Source file src/oss.terrastruct.com/d2/d2layouts/d2dagrelayout/layout.go

Documentation: oss.terrastruct.com/d2/d2layouts/d2dagrelayout

     1  package d2dagrelayout
     2  
     3  import (
     4  	"context"
     5  	_ "embed"
     6  	"encoding/json"
     7  	"fmt"
     8  	"math"
     9  	"sort"
    10  	"strings"
    11  
    12  	"cdr.dev/slog"
    13  	"github.com/dop251/goja"
    14  
    15  	"oss.terrastruct.com/util-go/xdefer"
    16  
    17  	"oss.terrastruct.com/util-go/go2"
    18  
    19  	"oss.terrastruct.com/d2/d2graph"
    20  	"oss.terrastruct.com/d2/d2target"
    21  	"oss.terrastruct.com/d2/lib/geo"
    22  	"oss.terrastruct.com/d2/lib/label"
    23  	"oss.terrastruct.com/d2/lib/log"
    24  	"oss.terrastruct.com/d2/lib/shape"
    25  )
    26  
    27  //go:embed setup.js
    28  var setupJS string
    29  
    30  //go:embed dagre.js
    31  var dagreJS string
    32  
    33  const (
    34  	MIN_RANK_SEP    = 60
    35  	EDGE_LABEL_GAP  = 20
    36  	DEFAULT_PADDING = 30.
    37  	MIN_SPACING     = 10.
    38  )
    39  
    40  type ConfigurableOpts struct {
    41  	NodeSep int `json:"nodesep"`
    42  	EdgeSep int `json:"edgesep"`
    43  }
    44  
    45  var DefaultOpts = ConfigurableOpts{
    46  	NodeSep: 60,
    47  	EdgeSep: 20,
    48  }
    49  
    50  type DagreNode struct {
    51  	ID     string  `json:"id"`
    52  	X      float64 `json:"x"`
    53  	Y      float64 `json:"y"`
    54  	Width  float64 `json:"width"`
    55  	Height float64 `json:"height"`
    56  }
    57  
    58  type DagreEdge struct {
    59  	Points []*geo.Point `json:"points"`
    60  }
    61  
    62  type dagreOpts struct {
    63  	// for a top to bottom graph: ranksep is y spacing, nodesep is x spacing, edgesep is x spacing
    64  	ranksep int
    65  	// graph direction: tb (top to bottom)| bt | lr | rl
    66  	rankdir string
    67  
    68  	ConfigurableOpts
    69  }
    70  
    71  func DefaultLayout(ctx context.Context, g *d2graph.Graph) (err error) {
    72  	return Layout(ctx, g, nil)
    73  }
    74  
    75  func Layout(ctx context.Context, g *d2graph.Graph, opts *ConfigurableOpts) (err error) {
    76  	if opts == nil {
    77  		opts = &DefaultOpts
    78  	}
    79  	defer xdefer.Errorf(&err, "failed to dagre layout")
    80  
    81  	debugJS := false
    82  	vm := goja.New()
    83  	if _, err := vm.RunString(dagreJS); err != nil {
    84  		return err
    85  	}
    86  	if _, err := vm.RunString(setupJS); err != nil {
    87  		return err
    88  	}
    89  
    90  	rootAttrs := dagreOpts{
    91  		ConfigurableOpts: ConfigurableOpts{
    92  			EdgeSep: opts.EdgeSep,
    93  			NodeSep: opts.NodeSep,
    94  		},
    95  	}
    96  	isHorizontal := false
    97  	switch g.Root.Direction.Value {
    98  	case "down":
    99  		rootAttrs.rankdir = "TB"
   100  	case "right":
   101  		rootAttrs.rankdir = "LR"
   102  		isHorizontal = true
   103  	case "left":
   104  		rootAttrs.rankdir = "RL"
   105  		isHorizontal = true
   106  	case "up":
   107  		rootAttrs.rankdir = "BT"
   108  	default:
   109  		rootAttrs.rankdir = "TB"
   110  	}
   111  
   112  	// set label and icon positions for dagre
   113  	for _, obj := range g.Objects {
   114  		positionLabelsIcons(obj)
   115  	}
   116  
   117  	maxLabelWidth := 0
   118  	maxLabelHeight := 0
   119  	for _, edge := range g.Edges {
   120  		width := edge.LabelDimensions.Width
   121  		height := edge.LabelDimensions.Height
   122  		maxLabelWidth = go2.Max(maxLabelWidth, width)
   123  		maxLabelHeight = go2.Max(maxLabelHeight, height)
   124  	}
   125  
   126  	if !isHorizontal {
   127  		rootAttrs.ranksep = go2.Max(100, maxLabelHeight+40)
   128  	} else {
   129  		rootAttrs.ranksep = go2.Max(100, maxLabelWidth+40)
   130  		// use existing config
   131  		// rootAttrs.NodeSep = rootAttrs.EdgeSep
   132  		// // configure vertical padding
   133  		// rootAttrs.EdgeSep = maxLabelHeight + 40
   134  		// Note: non-containers have both of these as padding (rootAttrs.NodeSep + rootAttrs.EdgeSep)
   135  	}
   136  
   137  	configJS := setGraphAttrs(rootAttrs)
   138  	if _, err := vm.RunString(configJS); err != nil {
   139  		return err
   140  	}
   141  
   142  	mapper := NewObjectMapper()
   143  	for _, obj := range g.Objects {
   144  		mapper.Register(obj)
   145  	}
   146  	loadScript := ""
   147  	for _, obj := range g.Objects {
   148  		loadScript += mapper.generateAddNodeLine(obj, int(obj.Width), int(obj.Height))
   149  		if obj.Parent != g.Root {
   150  			loadScript += mapper.generateAddParentLine(obj, obj.Parent)
   151  		}
   152  	}
   153  
   154  	for _, edge := range g.Edges {
   155  		src, dst := getEdgeEndpoints(g, edge)
   156  
   157  		width := edge.LabelDimensions.Width
   158  		height := edge.LabelDimensions.Height
   159  
   160  		numEdges := 0
   161  		for _, e := range g.Edges {
   162  			otherSrc, otherDst := getEdgeEndpoints(g, e)
   163  			if (otherSrc == src && otherDst == dst) || (otherSrc == dst && otherDst == src) {
   164  				numEdges++
   165  			}
   166  		}
   167  
   168  		// We want to leave some gap between multiple edges
   169  		if numEdges > 1 {
   170  			switch g.Root.Direction.Value {
   171  			case "down", "up", "":
   172  				width += EDGE_LABEL_GAP
   173  			case "left", "right":
   174  				height += EDGE_LABEL_GAP
   175  			}
   176  		}
   177  
   178  		loadScript += mapper.generateAddEdgeLine(src, dst, edge.AbsID(), width, height)
   179  	}
   180  
   181  	if debugJS {
   182  		log.Debug(ctx, "script", slog.F("all", setupJS+configJS+loadScript))
   183  	}
   184  
   185  	if _, err := vm.RunString(loadScript); err != nil {
   186  		return err
   187  	}
   188  
   189  	if _, err := vm.RunString(`dagre.layout(g)`); err != nil {
   190  		if debugJS {
   191  			log.Warn(ctx, "layout error", slog.F("err", err))
   192  		}
   193  		return err
   194  	}
   195  
   196  	for i := range g.Objects {
   197  		val, err := vm.RunString(fmt.Sprintf("JSON.stringify(g.node(g.nodes()[%d]))", i))
   198  		if err != nil {
   199  			return err
   200  		}
   201  		var dn DagreNode
   202  		if err := json.Unmarshal([]byte(val.String()), &dn); err != nil {
   203  			return err
   204  		}
   205  		if debugJS {
   206  			log.Debug(ctx, "graph", slog.F("json", dn))
   207  		}
   208  
   209  		obj := mapper.ToObj(dn.ID)
   210  
   211  		// dagre gives center of node
   212  		obj.TopLeft = geo.NewPoint(math.Round(dn.X-dn.Width/2), math.Round(dn.Y-dn.Height/2))
   213  		obj.Width = math.Ceil(dn.Width)
   214  		obj.Height = math.Ceil(dn.Height)
   215  	}
   216  
   217  	for i, edge := range g.Edges {
   218  		val, err := vm.RunString(fmt.Sprintf("JSON.stringify(g.edge(g.edges()[%d]))", i))
   219  		if err != nil {
   220  			return err
   221  		}
   222  		var de DagreEdge
   223  		if err := json.Unmarshal([]byte(val.String()), &de); err != nil {
   224  			return err
   225  		}
   226  		if debugJS {
   227  			log.Debug(ctx, "graph", slog.F("json", de))
   228  		}
   229  
   230  		points := make([]*geo.Point, len(de.Points))
   231  		for i := range de.Points {
   232  			if edge.SrcArrow && !edge.DstArrow {
   233  				points[len(de.Points)-i-1] = de.Points[i].Copy()
   234  			} else {
   235  				points[i] = de.Points[i].Copy()
   236  			}
   237  		}
   238  
   239  		startIndex, endIndex := 0, len(points)-1
   240  		start, end := points[startIndex], points[endIndex]
   241  
   242  		// chop where edge crosses the source/target boxes since container edges were routed to a descendant
   243  		if edge.Src != edge.Dst {
   244  			for i := 1; i < len(points); i++ {
   245  				segment := *geo.NewSegment(points[i-1], points[i])
   246  				if intersections := edge.Src.Box.Intersections(segment); len(intersections) > 0 {
   247  					start = intersections[0]
   248  					startIndex = i - 1
   249  				}
   250  
   251  				if intersections := edge.Dst.Box.Intersections(segment); len(intersections) > 0 {
   252  					end = intersections[0]
   253  					endIndex = i
   254  					break
   255  				}
   256  			}
   257  		}
   258  		points = points[startIndex : endIndex+1]
   259  		points[0] = start
   260  		points[len(points)-1] = end
   261  
   262  		edge.Route = points
   263  	}
   264  
   265  	adjustRankSpacing(g, float64(rootAttrs.ranksep), isHorizontal)
   266  	adjustCrossRankSpacing(g, float64(rootAttrs.ranksep), !isHorizontal)
   267  	fitContainerPadding(g, float64(rootAttrs.ranksep), isHorizontal)
   268  
   269  	for _, edge := range g.Edges {
   270  		points := edge.Route
   271  		startIndex, endIndex := 0, len(points)-1
   272  		start, end := points[startIndex], points[endIndex]
   273  
   274  		// arrowheads can appear broken if segments are very short from dagre routing a point just outside the shape
   275  		// to fix this, we try extending the previous segment into the shape instead of having a very short segment
   276  		if startIndex+2 < len(points) {
   277  			newStartingSegment := *geo.NewSegment(start, points[startIndex+1])
   278  			if newStartingSegment.Length() < d2graph.MIN_SEGMENT_LEN {
   279  				// we don't want a very short segment right next to the source because it will mess up the arrowhead
   280  				// instead we want to extend the next segment into the shape border if possible
   281  				nextStart := points[startIndex+1]
   282  				nextEnd := points[startIndex+2]
   283  
   284  				// Note: in other direction to extend towards source
   285  				nextSegment := *geo.NewSegment(nextStart, nextEnd)
   286  				v := nextSegment.ToVector()
   287  				extendedStart := nextEnd.ToVector().Add(v.AddLength(d2graph.MIN_SEGMENT_LEN)).ToPoint()
   288  				extended := *geo.NewSegment(nextEnd, extendedStart)
   289  
   290  				if intersections := edge.Src.Box.Intersections(extended); len(intersections) > 0 {
   291  					startIndex++
   292  					points[startIndex] = intersections[0]
   293  					start = points[startIndex]
   294  				}
   295  			}
   296  		}
   297  		if endIndex-2 >= 0 {
   298  			newEndingSegment := *geo.NewSegment(end, points[endIndex-1])
   299  			if newEndingSegment.Length() < d2graph.MIN_SEGMENT_LEN {
   300  				// extend the prev segment into the shape border if possible
   301  				prevStart := points[endIndex-2]
   302  				prevEnd := points[endIndex-1]
   303  
   304  				prevSegment := *geo.NewSegment(prevStart, prevEnd)
   305  				v := prevSegment.ToVector()
   306  				extendedEnd := prevStart.ToVector().Add(v.AddLength(d2graph.MIN_SEGMENT_LEN)).ToPoint()
   307  				extended := *geo.NewSegment(prevStart, extendedEnd)
   308  
   309  				if intersections := edge.Dst.Box.Intersections(extended); len(intersections) > 0 {
   310  					endIndex--
   311  					points[endIndex] = intersections[0]
   312  					end = points[endIndex]
   313  				}
   314  			}
   315  		}
   316  
   317  		var originalSrcTL, originalDstTL *geo.Point
   318  		// if the edge passes through 3d/multiple, use the offset box for tracing to border
   319  		if srcDx, srcDy := edge.Src.GetModifierElementAdjustments(); srcDx != 0 || srcDy != 0 {
   320  			if start.X > edge.Src.TopLeft.X+srcDx &&
   321  				start.Y < edge.Src.TopLeft.Y+edge.Src.Height-srcDy {
   322  				originalSrcTL = edge.Src.TopLeft.Copy()
   323  				edge.Src.TopLeft.X += srcDx
   324  				edge.Src.TopLeft.Y -= srcDy
   325  			}
   326  		}
   327  		if dstDx, dstDy := edge.Dst.GetModifierElementAdjustments(); dstDx != 0 || dstDy != 0 {
   328  			if end.X > edge.Dst.TopLeft.X+dstDx &&
   329  				end.Y < edge.Dst.TopLeft.Y+edge.Dst.Height-dstDy {
   330  				originalDstTL = edge.Dst.TopLeft.Copy()
   331  				edge.Dst.TopLeft.X += dstDx
   332  				edge.Dst.TopLeft.Y -= dstDy
   333  			}
   334  		}
   335  
   336  		startIndex, endIndex = edge.TraceToShape(points, startIndex, endIndex)
   337  		points = points[startIndex : endIndex+1]
   338  
   339  		// build a curved path from the dagre route
   340  		vectors := make([]geo.Vector, 0, len(points)-1)
   341  		for i := 1; i < len(points); i++ {
   342  			vectors = append(vectors, points[i-1].VectorTo(points[i]))
   343  		}
   344  
   345  		path := make([]*geo.Point, 0)
   346  		path = append(path, points[0])
   347  		if len(vectors) > 1 {
   348  			path = append(path, points[0].AddVector(vectors[0].Multiply(.8)))
   349  			for i := 1; i < len(vectors)-2; i++ {
   350  				p := points[i]
   351  				v := vectors[i]
   352  				path = append(path, p.AddVector(v.Multiply(.2)))
   353  				path = append(path, p.AddVector(v.Multiply(.5)))
   354  				path = append(path, p.AddVector(v.Multiply(.8)))
   355  			}
   356  			path = append(path, points[len(points)-2].AddVector(vectors[len(vectors)-1].Multiply(.2)))
   357  			edge.IsCurve = true
   358  		}
   359  		path = append(path, points[len(points)-1])
   360  
   361  		edge.Route = path
   362  		// compile needs to assign edge label positions
   363  		if edge.Label.Value != "" {
   364  			edge.LabelPosition = go2.Pointer(label.InsideMiddleCenter.String())
   365  		}
   366  
   367  		// undo 3d/multiple offset
   368  		if originalSrcTL != nil {
   369  			edge.Src.TopLeft.X = originalSrcTL.X
   370  			edge.Src.TopLeft.Y = originalSrcTL.Y
   371  		}
   372  		if originalDstTL != nil {
   373  			edge.Dst.TopLeft.X = originalDstTL.X
   374  			edge.Dst.TopLeft.Y = originalDstTL.Y
   375  		}
   376  	}
   377  
   378  	return nil
   379  }
   380  
   381  func getEdgeEndpoints(g *d2graph.Graph, edge *d2graph.Edge) (*d2graph.Object, *d2graph.Object) {
   382  	// dagre doesn't work with edges to containers so we connect container edges to their first child instead (going all the way down)
   383  	// we will chop the edge where it intersects the container border so it only shows the edge from the container
   384  	src := edge.Src
   385  	for len(src.Children) > 0 && src.Class == nil && src.SQLTable == nil {
   386  		// We want to get the bottom node of sources, setting its rank higher than all children
   387  		src = getLongestEdgeChainTail(g, src)
   388  	}
   389  	dst := edge.Dst
   390  	for len(dst.Children) > 0 && dst.Class == nil && dst.SQLTable == nil {
   391  		dst = getLongestEdgeChainHead(g, dst)
   392  	}
   393  	if edge.SrcArrow && !edge.DstArrow {
   394  		// for `b <- a`, edge.Edge is `a -> b` and we expect this routing result
   395  		src, dst = dst, src
   396  	}
   397  	return src, dst
   398  }
   399  
   400  func setGraphAttrs(attrs dagreOpts) string {
   401  	return fmt.Sprintf(`g.setGraph({
   402    ranksep: %d,
   403    edgesep: %d,
   404    nodesep: %d,
   405    rankdir: "%s",
   406  });
   407  `,
   408  		attrs.ranksep,
   409  		attrs.ConfigurableOpts.EdgeSep,
   410  		attrs.ConfigurableOpts.NodeSep,
   411  		attrs.rankdir,
   412  	)
   413  }
   414  
   415  // getLongestEdgeChainHead finds the longest chain in a container and gets its head
   416  // If there are multiple chains of the same length, get the head closest to the center
   417  func getLongestEdgeChainHead(g *d2graph.Graph, container *d2graph.Object) *d2graph.Object {
   418  	rank := make(map[*d2graph.Object]int)
   419  	chainLength := make(map[*d2graph.Object]int)
   420  
   421  	for _, obj := range container.ChildrenArray {
   422  		isHead := true
   423  		for _, e := range g.Edges {
   424  			if inContainer(e.Src, container) != nil && inContainer(e.Dst, obj) != nil {
   425  				isHead = false
   426  				break
   427  			}
   428  		}
   429  		if !isHead {
   430  			continue
   431  		}
   432  		rank[obj] = 1
   433  		chainLength[obj] = 1
   434  		// BFS
   435  		queue := []*d2graph.Object{obj}
   436  		visited := make(map[*d2graph.Object]struct{})
   437  		for len(queue) > 0 {
   438  			curr := queue[0]
   439  			queue = queue[1:]
   440  			if _, ok := visited[curr]; ok {
   441  				continue
   442  			}
   443  			visited[curr] = struct{}{}
   444  			for _, e := range g.Edges {
   445  				child := inContainer(e.Dst, container)
   446  				if child == curr {
   447  					continue
   448  				}
   449  				if child != nil && inContainer(e.Src, curr) != nil {
   450  					if rank[curr]+1 > rank[child] {
   451  						rank[child] = rank[curr] + 1
   452  						chainLength[obj] = go2.Max(chainLength[obj], rank[child])
   453  					}
   454  					queue = append(queue, child)
   455  				}
   456  			}
   457  		}
   458  	}
   459  	max := int(math.MinInt32)
   460  	for _, obj := range container.ChildrenArray {
   461  		if chainLength[obj] > max {
   462  			max = chainLength[obj]
   463  		}
   464  	}
   465  
   466  	var heads []*d2graph.Object
   467  	for i, obj := range container.ChildrenArray {
   468  		if rank[obj] == 1 && chainLength[obj] == max {
   469  			heads = append(heads, container.ChildrenArray[i])
   470  		}
   471  	}
   472  
   473  	if len(heads) > 0 {
   474  		return heads[int(math.Floor(float64(len(heads))/2.0))]
   475  	}
   476  	return container.ChildrenArray[0]
   477  }
   478  
   479  // getLongestEdgeChainTail gets the node at the end of the longest edge chain, because that will be the end of the container
   480  // and is what external connections should connect with.
   481  // If there are multiple of same length, get the one closest to the middle
   482  func getLongestEdgeChainTail(g *d2graph.Graph, container *d2graph.Object) *d2graph.Object {
   483  	rank := make(map[*d2graph.Object]int)
   484  
   485  	for _, obj := range container.ChildrenArray {
   486  		isHead := true
   487  		for _, e := range g.Edges {
   488  			if inContainer(e.Src, container) != nil && inContainer(e.Dst, obj) != nil {
   489  				isHead = false
   490  				break
   491  			}
   492  		}
   493  		if !isHead {
   494  			continue
   495  		}
   496  		rank[obj] = 1
   497  		// BFS
   498  		queue := []*d2graph.Object{obj}
   499  		visited := make(map[*d2graph.Object]struct{})
   500  		for len(queue) > 0 {
   501  			curr := queue[0]
   502  			queue = queue[1:]
   503  			if _, ok := visited[curr]; ok {
   504  				continue
   505  			}
   506  			visited[curr] = struct{}{}
   507  			for _, e := range g.Edges {
   508  				child := inContainer(e.Dst, container)
   509  				if child == curr {
   510  					continue
   511  				}
   512  				if child != nil && inContainer(e.Src, curr) != nil {
   513  					rank[child] = go2.Max(rank[child], rank[curr]+1)
   514  					queue = append(queue, child)
   515  				}
   516  			}
   517  		}
   518  	}
   519  	max := int(math.MinInt32)
   520  	for _, obj := range container.ChildrenArray {
   521  		if rank[obj] > max {
   522  			max = rank[obj]
   523  		}
   524  	}
   525  
   526  	var tails []*d2graph.Object
   527  	for i, obj := range container.ChildrenArray {
   528  		if rank[obj] == max {
   529  			tails = append(tails, container.ChildrenArray[i])
   530  		}
   531  	}
   532  
   533  	return tails[int(math.Floor(float64(len(tails))/2.0))]
   534  }
   535  
   536  func inContainer(obj, container *d2graph.Object) *d2graph.Object {
   537  	if obj == nil {
   538  		return nil
   539  	}
   540  	if obj == container {
   541  		return obj
   542  	}
   543  	if obj.Parent == container {
   544  		return obj
   545  	}
   546  	return inContainer(obj.Parent, container)
   547  }
   548  
   549  func positionLabelsIcons(obj *d2graph.Object) {
   550  	if obj.Icon != nil && obj.IconPosition == nil {
   551  		if len(obj.ChildrenArray) > 0 {
   552  			obj.IconPosition = go2.Pointer(label.OutsideTopLeft.String())
   553  			if obj.LabelPosition == nil {
   554  				obj.LabelPosition = go2.Pointer(label.OutsideTopRight.String())
   555  				return
   556  			}
   557  		} else if obj.SQLTable != nil || obj.Class != nil || obj.Language != "" {
   558  			obj.IconPosition = go2.Pointer(label.OutsideTopLeft.String())
   559  		} else {
   560  			obj.IconPosition = go2.Pointer(label.InsideMiddleCenter.String())
   561  		}
   562  	}
   563  	if obj.HasLabel() && obj.LabelPosition == nil {
   564  		if len(obj.ChildrenArray) > 0 {
   565  			obj.LabelPosition = go2.Pointer(label.OutsideTopCenter.String())
   566  		} else if obj.HasOutsideBottomLabel() {
   567  			obj.LabelPosition = go2.Pointer(label.OutsideBottomCenter.String())
   568  		} else if obj.Icon != nil {
   569  			obj.LabelPosition = go2.Pointer(label.InsideTopCenter.String())
   570  		} else {
   571  			obj.LabelPosition = go2.Pointer(label.InsideMiddleCenter.String())
   572  		}
   573  	}
   574  }
   575  
   576  func getRanks(g *d2graph.Graph, isHorizontal bool) (ranks [][]*d2graph.Object, objectRanks, startingParentRanks, endingParentRanks map[*d2graph.Object]int) {
   577  	alignedObjects := make(map[float64][]*d2graph.Object)
   578  	for _, obj := range g.Objects {
   579  		if !obj.IsContainer() {
   580  			if !isHorizontal {
   581  				y := math.Ceil(obj.TopLeft.Y + obj.Height/2)
   582  				alignedObjects[y] = append(alignedObjects[y], obj)
   583  			} else {
   584  				x := math.Ceil(obj.TopLeft.X + obj.Width/2)
   585  				alignedObjects[x] = append(alignedObjects[x], obj)
   586  			}
   587  		}
   588  	}
   589  
   590  	levels := make([]float64, 0, len(alignedObjects))
   591  	for l := range alignedObjects {
   592  		levels = append(levels, l)
   593  	}
   594  	sort.Slice(levels, func(i, j int) bool {
   595  		return levels[i] < levels[j]
   596  	})
   597  
   598  	ranks = make([][]*d2graph.Object, 0, len(levels))
   599  	objectRanks = make(map[*d2graph.Object]int)
   600  	for i, l := range levels {
   601  		for _, obj := range alignedObjects[l] {
   602  			objectRanks[obj] = i
   603  		}
   604  		ranks = append(ranks, alignedObjects[l])
   605  	}
   606  
   607  	startingParentRanks = make(map[*d2graph.Object]int)
   608  	endingParentRanks = make(map[*d2graph.Object]int)
   609  	for _, obj := range g.Objects {
   610  		if obj.IsContainer() {
   611  			continue
   612  		}
   613  		r := objectRanks[obj]
   614  		// update all ancestor's min/max ranks
   615  		for parent := obj.Parent; parent != nil && parent != g.Root; parent = parent.Parent {
   616  			if start, has := startingParentRanks[parent]; !has || r < start {
   617  				startingParentRanks[parent] = r
   618  			}
   619  			if end, has := endingParentRanks[parent]; !has || r > end {
   620  				endingParentRanks[parent] = r
   621  			}
   622  		}
   623  	}
   624  
   625  	return ranks, objectRanks, startingParentRanks, endingParentRanks
   626  }
   627  
   628  // shift everything down by distance if it is at or below start position
   629  func shiftDown(g *d2graph.Graph, start, distance float64, isHorizontal bool) {
   630  	if isHorizontal {
   631  		for _, edge := range g.Edges {
   632  			first, last := edge.Route[0], edge.Route[len(edge.Route)-1]
   633  			if start <= first.X {
   634  				onStaticSrc := first.X == edge.Src.TopLeft.X+edge.Src.Width && edge.Src.TopLeft.X < start
   635  				if !onStaticSrc {
   636  					// src is not shifting and we are on src so don't shift
   637  					first.X += distance
   638  				}
   639  			}
   640  			if start <= last.X {
   641  				onStaticDst := last.X == edge.Dst.TopLeft.X+edge.Dst.Width && edge.Dst.TopLeft.X < start
   642  				if !onStaticDst {
   643  					last.X += distance
   644  				}
   645  			}
   646  			for i := 1; i < len(edge.Route)-1; i++ {
   647  				p := edge.Route[i]
   648  				if p.X < start {
   649  					continue
   650  				}
   651  				p.X += distance
   652  			}
   653  		}
   654  		for _, obj := range g.Objects {
   655  			if obj.TopLeft.X < start {
   656  				continue
   657  			}
   658  			obj.TopLeft.X += distance
   659  		}
   660  	} else {
   661  		for _, edge := range g.Edges {
   662  			first, last := edge.Route[0], edge.Route[len(edge.Route)-1]
   663  			if start <= first.Y {
   664  				onStaticSrc := first.Y == edge.Src.TopLeft.Y+edge.Src.Height && edge.Src.TopLeft.Y < start
   665  				if !onStaticSrc {
   666  					// src is not shifting and we are on src so don't shift
   667  					first.Y += distance
   668  				}
   669  			}
   670  			if start <= last.Y {
   671  				onStaticDst := last.Y == edge.Dst.TopLeft.Y+edge.Dst.Height && edge.Dst.TopLeft.Y < start
   672  				if !onStaticDst {
   673  					last.Y += distance
   674  				}
   675  			}
   676  			for i := 1; i < len(edge.Route)-1; i++ {
   677  				p := edge.Route[i]
   678  				if p.Y < start {
   679  					continue
   680  				}
   681  				p.Y += distance
   682  			}
   683  		}
   684  		for _, obj := range g.Objects {
   685  			if obj.TopLeft.Y < start {
   686  				continue
   687  			}
   688  			obj.TopLeft.Y += distance
   689  		}
   690  	}
   691  }
   692  
   693  func shiftUp(g *d2graph.Graph, start, distance float64, isHorizontal bool) {
   694  	if isHorizontal {
   695  		for _, edge := range g.Edges {
   696  			first, last := edge.Route[0], edge.Route[len(edge.Route)-1]
   697  			if first.X <= start {
   698  				onStaticSrc := first.X == edge.Src.TopLeft.X && start < edge.Src.TopLeft.X+edge.Src.Width
   699  				if !onStaticSrc {
   700  					// src is not shifting and we are on src so don't shift
   701  					first.X -= distance
   702  				}
   703  			}
   704  			if last.X <= start {
   705  				onStaticDst := last.X == edge.Dst.TopLeft.X && start < edge.Dst.TopLeft.X+edge.Dst.Width
   706  				if !onStaticDst {
   707  					last.X -= distance
   708  				}
   709  			}
   710  			for i := 1; i < len(edge.Route)-1; i++ {
   711  				p := edge.Route[i]
   712  				if start < p.X {
   713  					continue
   714  				}
   715  				p.X -= distance
   716  			}
   717  		}
   718  		for _, obj := range g.Objects {
   719  			if start < obj.TopLeft.X {
   720  				continue
   721  			}
   722  			obj.TopLeft.X -= distance
   723  		}
   724  	} else {
   725  		for _, edge := range g.Edges {
   726  			first, last := edge.Route[0], edge.Route[len(edge.Route)-1]
   727  			if first.Y <= start {
   728  				// don't shift first edge point if src is not shifting and we are on src
   729  				onStaticSrc := first.Y == edge.Src.TopLeft.Y && start < edge.Src.TopLeft.Y+edge.Src.Height
   730  				if !onStaticSrc {
   731  					first.Y -= distance
   732  				}
   733  			}
   734  			if last.Y <= start {
   735  				onStaticDst := last.Y == edge.Dst.TopLeft.Y && start < edge.Dst.TopLeft.Y
   736  				if !onStaticDst {
   737  					last.Y -= distance
   738  				}
   739  			}
   740  			for i := 1; i < len(edge.Route)-1; i++ {
   741  				p := edge.Route[i]
   742  				// for _, p := range edge.Route {
   743  				if start < p.Y {
   744  					continue
   745  				}
   746  				p.Y -= distance
   747  			}
   748  		}
   749  		for _, obj := range g.Objects {
   750  			if start < obj.TopLeft.Y {
   751  				continue
   752  			}
   753  			obj.TopLeft.Y -= distance
   754  		}
   755  	}
   756  }
   757  
   758  // shift down everything that is below start
   759  // shift all nodes that are reachable via an edge or being directly below a shifting node or expanding container
   760  // expand containers to wrap shifted nodes
   761  func shiftReachableDown(g *d2graph.Graph, obj *d2graph.Object, start, distance float64, isHorizontal, isMargin bool) map[*d2graph.Object]struct{} {
   762  	q := []*d2graph.Object{obj}
   763  
   764  	needsMove := make(map[*d2graph.Object]struct{})
   765  	seen := make(map[*d2graph.Object]struct{})
   766  	shifted := make(map[*d2graph.Object]struct{})
   767  	shiftedEdges := make(map[*d2graph.Edge]struct{})
   768  	queue := func(o *d2graph.Object) {
   769  		if _, in := seen[o]; in {
   770  			return
   771  		}
   772  		q = append(q, o)
   773  	}
   774  
   775  	// if object below is within this distance after shifting, also shift it
   776  	threshold := 100.
   777  	checkBelow := func(curr *d2graph.Object) {
   778  		currBottom := curr.TopLeft.Y + curr.Height
   779  		currRight := curr.TopLeft.X + curr.Width
   780  		if isHorizontal {
   781  			originalRight := currRight
   782  			if _, in := shifted[curr]; in {
   783  				originalRight -= distance
   784  			}
   785  			for _, other := range g.Objects {
   786  				if other == curr || curr.IsDescendantOf(other) {
   787  					continue
   788  				}
   789  				if originalRight < other.TopLeft.X &&
   790  					other.TopLeft.X < originalRight+distance+threshold &&
   791  					curr.TopLeft.Y < other.TopLeft.Y+other.Height &&
   792  					other.TopLeft.Y < currBottom {
   793  					queue(other)
   794  				}
   795  			}
   796  		} else {
   797  			originalBottom := currBottom
   798  			if _, in := shifted[curr]; in {
   799  				originalBottom -= distance
   800  			}
   801  			for _, other := range g.Objects {
   802  				if other == curr || curr.IsDescendantOf(other) {
   803  					continue
   804  				}
   805  				if originalBottom < other.TopLeft.Y &&
   806  					other.TopLeft.Y < originalBottom+distance+threshold &&
   807  					curr.TopLeft.X < other.TopLeft.X+other.Width &&
   808  					other.TopLeft.X < currRight {
   809  					queue(other)
   810  				}
   811  			}
   812  		}
   813  	}
   814  
   815  	processQueue := func() {
   816  		for len(q) > 0 {
   817  			curr := q[0]
   818  			q = q[1:]
   819  			if _, was := seen[curr]; was {
   820  				continue
   821  			}
   822  			// skip other objects behind start
   823  			if curr != obj {
   824  				if _, in := needsMove[curr]; !in {
   825  					if isHorizontal {
   826  						if curr.TopLeft.X < start {
   827  							continue
   828  						}
   829  					} else {
   830  						if curr.TopLeft.Y < start {
   831  							continue
   832  						}
   833  					}
   834  				}
   835  			}
   836  
   837  			if isHorizontal {
   838  				_, shift := needsMove[curr]
   839  				if !shift {
   840  					if !isMargin {
   841  						shift = start < curr.TopLeft.X
   842  					} else {
   843  						shift = start <= curr.TopLeft.X
   844  					}
   845  				}
   846  
   847  				if shift {
   848  					curr.TopLeft.X += distance
   849  					shifted[curr] = struct{}{}
   850  				}
   851  			} else {
   852  				_, shift := needsMove[curr]
   853  				if !shift {
   854  					if !isMargin {
   855  						shift = start < curr.TopLeft.Y
   856  					} else {
   857  						shift = start <= curr.TopLeft.Y
   858  					}
   859  				}
   860  				if shift {
   861  					curr.TopLeft.Y += distance
   862  					shifted[curr] = struct{}{}
   863  				}
   864  			}
   865  			seen[curr] = struct{}{}
   866  
   867  			if curr.Parent != g.Root && !curr.IsDescendantOf(obj) {
   868  				queue(curr.Parent)
   869  			}
   870  
   871  			for _, child := range curr.ChildrenArray {
   872  				queue(child)
   873  			}
   874  
   875  			for _, e := range g.Edges {
   876  				if _, in := shiftedEdges[e]; in {
   877  					continue
   878  				}
   879  				if e.Src == curr && e.Dst == curr {
   880  					if isHorizontal {
   881  						for _, p := range e.Route {
   882  							p.X += distance
   883  						}
   884  					} else {
   885  						for _, p := range e.Route {
   886  							p.Y += distance
   887  						}
   888  					}
   889  					shiftedEdges[e] = struct{}{}
   890  					continue
   891  				} else if e.Src == curr {
   892  					last := e.Route[len(e.Route)-1]
   893  					if isHorizontal {
   894  						if start <= last.X &&
   895  							e.Dst.TopLeft.X+e.Dst.Width < last.X+distance {
   896  							needsMove[e.Dst] = struct{}{}
   897  						}
   898  					} else {
   899  						if start <= last.Y &&
   900  							e.Dst.TopLeft.Y+e.Dst.Height < last.Y+distance {
   901  							needsMove[e.Dst] = struct{}{}
   902  						}
   903  					}
   904  					queue(e.Dst)
   905  					first := e.Route[0]
   906  					startIndex := 0
   907  					_, wasShifted := shifted[curr]
   908  					if isHorizontal {
   909  						if wasShifted && first.X < curr.TopLeft.X && first.X < start {
   910  							first.X += distance
   911  							startIndex++
   912  						}
   913  						for i := startIndex; i < len(e.Route); i++ {
   914  							p := e.Route[i]
   915  							if start <= p.X {
   916  								p.X += distance
   917  							}
   918  						}
   919  					} else {
   920  						if wasShifted && first.Y < curr.TopLeft.Y && first.Y < start {
   921  							first.Y += distance
   922  							startIndex++
   923  						}
   924  						for i := startIndex; i < len(e.Route); i++ {
   925  							p := e.Route[i]
   926  							if start <= p.Y {
   927  								p.Y += distance
   928  							}
   929  						}
   930  					}
   931  					shiftedEdges[e] = struct{}{}
   932  				} else if e.Dst == curr {
   933  					first := e.Route[0]
   934  					if isHorizontal {
   935  						if start <= first.X &&
   936  							e.Src.TopLeft.X+e.Src.Width < first.X+distance {
   937  							needsMove[e.Src] = struct{}{}
   938  						}
   939  					} else {
   940  						if start <= first.Y &&
   941  							e.Src.TopLeft.Y+e.Src.Height < first.Y+distance {
   942  							needsMove[e.Src] = struct{}{}
   943  						}
   944  					}
   945  					queue(e.Src)
   946  					last := e.Route[len(e.Route)-1]
   947  					endIndex := len(e.Route)
   948  					_, wasShifted := shifted[curr]
   949  					if isHorizontal {
   950  						if wasShifted && last.X < curr.TopLeft.X && last.X < start {
   951  							last.X += distance
   952  							endIndex--
   953  						}
   954  						for i := 0; i < endIndex; i++ {
   955  							p := e.Route[i]
   956  							if start <= p.X {
   957  								p.X += distance
   958  							}
   959  						}
   960  					} else {
   961  						if wasShifted && last.Y < curr.TopLeft.Y && last.Y < start {
   962  							last.Y += distance
   963  							endIndex--
   964  						}
   965  						for i := 0; i < endIndex; i++ {
   966  							p := e.Route[i]
   967  							if start <= p.Y {
   968  								p.Y += distance
   969  							}
   970  						}
   971  					}
   972  					shiftedEdges[e] = struct{}{}
   973  				}
   974  			}
   975  
   976  			// check for nodes below that need to move from the shift
   977  			checkBelow(curr)
   978  		}
   979  	}
   980  
   981  	processQueue()
   982  
   983  	grown := make(map[*d2graph.Object]struct{})
   984  	for o := range seen {
   985  		if o.Parent == g.Root {
   986  			continue
   987  		}
   988  		if _, in := shifted[o.Parent]; in {
   989  			continue
   990  		}
   991  		if _, in := grown[o.Parent]; in {
   992  			continue
   993  		}
   994  
   995  		for parent := o.Parent; parent != g.Root; parent = parent.Parent {
   996  			if _, in := shifted[parent]; in {
   997  				break
   998  			}
   999  			if _, in := grown[parent]; in {
  1000  				break
  1001  			}
  1002  
  1003  			if isHorizontal {
  1004  				if parent.TopLeft.X < start {
  1005  					parent.Width += distance
  1006  					grown[parent] = struct{}{}
  1007  
  1008  					checkBelow(parent)
  1009  					processQueue()
  1010  				}
  1011  			} else {
  1012  				if parent.TopLeft.Y < start {
  1013  					parent.Height += distance
  1014  					grown[parent] = struct{}{}
  1015  
  1016  					checkBelow(parent)
  1017  					processQueue()
  1018  				}
  1019  			}
  1020  		}
  1021  	}
  1022  
  1023  	increasedMargins := make(map[*d2graph.Object]struct{})
  1024  	movedObjects := make([]*d2graph.Object, 0, len(shifted))
  1025  	for obj := range shifted {
  1026  		movedObjects = append(movedObjects, obj)
  1027  	}
  1028  	for obj := range grown {
  1029  		movedObjects = append(movedObjects, obj)
  1030  	}
  1031  	for _, moved := range movedObjects {
  1032  		counts := true
  1033  		// check if any other shifted is directly above
  1034  		for _, other := range movedObjects {
  1035  			if other == moved {
  1036  				continue
  1037  			}
  1038  			if isHorizontal {
  1039  				if other.TopLeft.Y+other.Height < moved.TopLeft.Y ||
  1040  					moved.TopLeft.Y+moved.Height < other.TopLeft.Y {
  1041  					// doesn't line up vertically
  1042  					continue
  1043  				}
  1044  
  1045  				// above and within threshold
  1046  				if other.TopLeft.X < moved.TopLeft.X &&
  1047  					moved.TopLeft.X < other.TopLeft.X+other.Width+threshold {
  1048  					counts = false
  1049  					break
  1050  				}
  1051  			} else {
  1052  				if other.TopLeft.X+other.Width < moved.TopLeft.X ||
  1053  					moved.TopLeft.X+moved.Width < other.TopLeft.X {
  1054  					// doesn't line up horizontally
  1055  					continue
  1056  				}
  1057  
  1058  				// above and within threshold
  1059  				if other.TopLeft.Y < moved.TopLeft.Y &&
  1060  					moved.TopLeft.Y < other.TopLeft.Y+other.Height+threshold {
  1061  					counts = false
  1062  					break
  1063  				}
  1064  			}
  1065  		}
  1066  		if counts {
  1067  			increasedMargins[moved] = struct{}{}
  1068  		}
  1069  	}
  1070  
  1071  	return increasedMargins
  1072  }
  1073  
  1074  func adjustRankSpacing(g *d2graph.Graph, rankSep float64, isHorizontal bool) {
  1075  	ranks, objectRanks, startingParentRanks, endingParentRanks := getRanks(g, isHorizontal)
  1076  
  1077  	// shifting bottom rank down first, then moving up to next rank
  1078  	for rank := len(ranks) - 1; rank >= 0; rank-- {
  1079  		var startingParents []*d2graph.Object
  1080  		var endingParents []*d2graph.Object
  1081  		for _, obj := range ranks[rank] {
  1082  			if obj.Parent == g.Root {
  1083  				continue
  1084  			}
  1085  			if r, has := endingParentRanks[obj.Parent]; has && r == rank {
  1086  				endingParents = append(endingParents, obj.Parent)
  1087  			}
  1088  			if r, has := startingParentRanks[obj.Parent]; has && r == rank {
  1089  				startingParents = append(startingParents, obj.Parent)
  1090  			}
  1091  		}
  1092  
  1093  		startingAncestorPositions := make(map[*d2graph.Object]float64)
  1094  		for len(startingParents) > 0 {
  1095  			var ancestors []*d2graph.Object
  1096  			for _, parent := range startingParents {
  1097  				_, padding := parent.Spacing()
  1098  				if _, has := startingAncestorPositions[parent]; !has {
  1099  					startingAncestorPositions[parent] = math.Inf(1)
  1100  				}
  1101  				var startPosition float64
  1102  				if isHorizontal {
  1103  					paddingIncrease := math.Max(0, padding.Left-rankSep/2)
  1104  					startPosition = parent.TopLeft.X - paddingIncrease
  1105  				} else {
  1106  					paddingIncrease := math.Max(0, padding.Top-rankSep/2)
  1107  					startPosition = parent.TopLeft.Y - paddingIncrease
  1108  				}
  1109  				startingAncestorPositions[parent] = math.Min(startingAncestorPositions[parent], startPosition)
  1110  				for _, child := range parent.ChildrenArray {
  1111  					if r, has := objectRanks[child]; has {
  1112  						if r != rank {
  1113  							continue
  1114  						}
  1115  					} else {
  1116  						if startingParentRanks[child] != rank {
  1117  							continue
  1118  						}
  1119  					}
  1120  					margin, _ := child.Spacing()
  1121  					if isHorizontal {
  1122  						startPosition = child.TopLeft.X - margin.Left - padding.Left
  1123  					} else {
  1124  						startPosition = child.TopLeft.Y - margin.Top - padding.Top
  1125  					}
  1126  					startingAncestorPositions[parent] = math.Min(startingAncestorPositions[parent], startPosition)
  1127  				}
  1128  				if parent.Parent != g.Root {
  1129  					ancestors = append(ancestors, parent.Parent)
  1130  				}
  1131  			}
  1132  			startingParents = ancestors
  1133  		}
  1134  
  1135  		endingAncestorPositions := make(map[*d2graph.Object]float64)
  1136  		for len(endingParents) > 0 {
  1137  			var ancestors []*d2graph.Object
  1138  			for _, parent := range endingParents {
  1139  				_, padding := parent.Spacing()
  1140  				if _, has := endingAncestorPositions[parent]; !has {
  1141  					endingAncestorPositions[parent] = math.Inf(-1)
  1142  				}
  1143  				var endPosition float64
  1144  				if isHorizontal {
  1145  					endPosition = parent.TopLeft.X + parent.Width + padding.Right - rankSep/2.
  1146  				} else {
  1147  					endPosition = parent.TopLeft.Y + parent.Height + padding.Bottom - rankSep/2.
  1148  				}
  1149  
  1150  				endingAncestorPositions[parent] = math.Max(endingAncestorPositions[parent], endPosition)
  1151  				for _, child := range parent.ChildrenArray {
  1152  					if r, has := objectRanks[child]; has {
  1153  						if r != rank {
  1154  							continue
  1155  						}
  1156  					} else {
  1157  						if endingParentRanks[child] != rank {
  1158  							continue
  1159  						}
  1160  					}
  1161  					margin, _ := child.Spacing()
  1162  
  1163  					if isHorizontal {
  1164  						endPosition = child.TopLeft.X + child.Width + margin.Right + padding.Right
  1165  					} else {
  1166  						endPosition = child.TopLeft.Y + child.Height + margin.Bottom + padding.Bottom
  1167  					}
  1168  					endingAncestorPositions[parent] = math.Max(endingAncestorPositions[parent], endPosition)
  1169  				}
  1170  				if parent.Parent != g.Root {
  1171  					ancestors = append(ancestors, parent.Parent)
  1172  				}
  1173  			}
  1174  			endingParents = ancestors
  1175  		}
  1176  
  1177  		startingAdjustmentOrder := make([]*d2graph.Object, 0, len(startingAncestorPositions))
  1178  		for ancestor := range startingAncestorPositions {
  1179  			startingAdjustmentOrder = append(startingAdjustmentOrder, ancestor)
  1180  		}
  1181  		// adjust starting ancestors top-down
  1182  		sort.Slice(startingAdjustmentOrder, func(i, j int) bool {
  1183  			iPos := startingAncestorPositions[startingAdjustmentOrder[i]]
  1184  			jPos := startingAncestorPositions[startingAdjustmentOrder[j]]
  1185  			return iPos < jPos
  1186  		})
  1187  
  1188  		endingAdjustmentOrder := make([]*d2graph.Object, 0, len(endingAncestorPositions))
  1189  		for ancestor := range endingAncestorPositions {
  1190  			endingAdjustmentOrder = append(endingAdjustmentOrder, ancestor)
  1191  		}
  1192  
  1193  		// adjust ending ancestors bottom-up
  1194  		sort.Slice(endingAdjustmentOrder, func(i, j int) bool {
  1195  			iPos := endingAncestorPositions[endingAdjustmentOrder[i]]
  1196  			jPos := endingAncestorPositions[endingAdjustmentOrder[j]]
  1197  			return jPos < iPos
  1198  		})
  1199  
  1200  		for _, ancestor := range endingAdjustmentOrder {
  1201  			var position float64
  1202  			if isHorizontal {
  1203  				position = ancestor.TopLeft.X + ancestor.Width
  1204  			} else {
  1205  				position = ancestor.TopLeft.Y + ancestor.Height
  1206  			}
  1207  			endDelta := endingAncestorPositions[ancestor] - position
  1208  			if endDelta > 0 {
  1209  				for _, obj := range g.Objects {
  1210  					if !obj.IsContainer() {
  1211  						continue
  1212  					}
  1213  					start := startingParentRanks[obj]
  1214  					end := endingParentRanks[obj]
  1215  					if start <= rank && rank <= end {
  1216  						if isHorizontal && position <= obj.TopLeft.X+obj.Width {
  1217  							obj.Width += endDelta
  1218  						} else if !isHorizontal &&
  1219  							position <= obj.TopLeft.Y+obj.Height {
  1220  							obj.Height += endDelta
  1221  						}
  1222  					}
  1223  				}
  1224  				shiftDown(g, position, endDelta, isHorizontal)
  1225  			}
  1226  		}
  1227  
  1228  		for _, ancestor := range startingAdjustmentOrder {
  1229  			var position float64
  1230  			if isHorizontal {
  1231  				position = ancestor.TopLeft.X
  1232  			} else {
  1233  				position = ancestor.TopLeft.Y
  1234  			}
  1235  			startDelta := position - startingAncestorPositions[ancestor]
  1236  			if startDelta > 0 {
  1237  				for _, obj := range g.Objects {
  1238  					if !obj.IsContainer() {
  1239  						continue
  1240  					}
  1241  					start := startingParentRanks[obj]
  1242  					end := endingParentRanks[obj]
  1243  					if start <= rank && rank <= end {
  1244  						if isHorizontal && obj.TopLeft.X <= position {
  1245  							obj.Width += startDelta
  1246  						} else if !isHorizontal && obj.TopLeft.Y <= position {
  1247  							obj.Height += startDelta
  1248  						}
  1249  					}
  1250  				}
  1251  				shiftUp(g, position, startDelta, isHorizontal)
  1252  			}
  1253  		}
  1254  	}
  1255  }
  1256  
  1257  func adjustCrossRankSpacing(g *d2graph.Graph, rankSep float64, isHorizontal bool) {
  1258  	var prevMarginTop, prevMarginBottom, prevMarginLeft, prevMarginRight map[*d2graph.Object]float64
  1259  	if isHorizontal {
  1260  		prevMarginLeft = make(map[*d2graph.Object]float64)
  1261  		prevMarginRight = make(map[*d2graph.Object]float64)
  1262  	} else {
  1263  		prevMarginTop = make(map[*d2graph.Object]float64)
  1264  		prevMarginBottom = make(map[*d2graph.Object]float64)
  1265  	}
  1266  	for _, obj := range g.Objects {
  1267  		if obj.IsGridDiagram() {
  1268  			continue
  1269  		}
  1270  		margin, padding := obj.Spacing()
  1271  		if !isHorizontal {
  1272  			if prevShift, has := prevMarginBottom[obj]; has {
  1273  				margin.Bottom -= prevShift
  1274  			}
  1275  			if margin.Bottom > 0 {
  1276  				increased := shiftReachableDown(g, obj, obj.TopLeft.Y+obj.Height, margin.Bottom, isHorizontal, true)
  1277  				for o := range increased {
  1278  					prevMarginBottom[o] = math.Max(prevMarginBottom[o], margin.Bottom)
  1279  				}
  1280  			}
  1281  			if padding.Bottom > 0 {
  1282  				shiftReachableDown(g, obj, obj.TopLeft.Y+obj.Height, padding.Bottom, isHorizontal, false)
  1283  				obj.Height += padding.Bottom
  1284  			}
  1285  			if prevShift, has := prevMarginTop[obj]; has {
  1286  				margin.Top -= prevShift
  1287  			}
  1288  			if margin.Top > 0 {
  1289  				increased := shiftReachableDown(g, obj, obj.TopLeft.Y, margin.Top, isHorizontal, true)
  1290  				for o := range increased {
  1291  					prevMarginTop[o] = math.Max(prevMarginTop[o], margin.Top)
  1292  				}
  1293  			}
  1294  			if padding.Top > 0 {
  1295  				shiftReachableDown(g, obj, obj.TopLeft.Y, padding.Top, isHorizontal, false)
  1296  				obj.Height += padding.Top
  1297  			}
  1298  		} else {
  1299  			if prevShift, has := prevMarginRight[obj]; has {
  1300  				margin.Right -= prevShift
  1301  			}
  1302  			if margin.Right > 0 {
  1303  				increased := shiftReachableDown(g, obj, obj.TopLeft.X+obj.Width, margin.Right, isHorizontal, true)
  1304  				for o := range increased {
  1305  					prevMarginRight[o] = math.Max(prevMarginRight[o], margin.Right)
  1306  				}
  1307  			}
  1308  			if padding.Right > 0 {
  1309  				shiftReachableDown(g, obj, obj.TopLeft.X+obj.Width, padding.Right, isHorizontal, false)
  1310  				obj.Width += padding.Right
  1311  			}
  1312  			if prevShift, has := prevMarginLeft[obj]; has {
  1313  				margin.Left -= prevShift
  1314  			}
  1315  			if margin.Left > 0 {
  1316  				increased := shiftReachableDown(g, obj, obj.TopLeft.X, margin.Left, isHorizontal, true)
  1317  				for o := range increased {
  1318  					prevMarginLeft[o] = math.Max(prevMarginLeft[o], margin.Left)
  1319  				}
  1320  			}
  1321  			if padding.Left > 0 {
  1322  				shiftReachableDown(g, obj, obj.TopLeft.X, padding.Left, isHorizontal, false)
  1323  				obj.Width += padding.Left
  1324  			}
  1325  		}
  1326  	}
  1327  }
  1328  
  1329  func fitContainerPadding(g *d2graph.Graph, rankSep float64, isHorizontal bool) {
  1330  	for _, obj := range g.Root.ChildrenArray {
  1331  		fitPadding(obj)
  1332  	}
  1333  }
  1334  
  1335  func fitPadding(obj *d2graph.Object) {
  1336  	dslShape := strings.ToLower(obj.Shape.Value)
  1337  	shapeType := d2target.DSL_SHAPE_TO_SHAPE_TYPE[dslShape]
  1338  	// Note: there's no shape-specific padding/placement in dagre yet
  1339  	if !obj.IsContainer() || shapeType != shape.SQUARE_TYPE {
  1340  		return
  1341  	}
  1342  	for _, child := range obj.ChildrenArray {
  1343  		fitPadding(child)
  1344  	}
  1345  
  1346  	// we will compute a perfectly fit innerBox merging our padding with children's margin,
  1347  	// but we need to add padding and margin together if an outside child label will overlap with our inside label
  1348  	_, padding := obj.Spacing()
  1349  	padding.Top = math.Max(padding.Top, DEFAULT_PADDING)
  1350  	padding.Bottom = math.Max(padding.Bottom, DEFAULT_PADDING)
  1351  	padding.Left = math.Max(padding.Left, DEFAULT_PADDING)
  1352  	padding.Right = math.Max(padding.Right, DEFAULT_PADDING)
  1353  
  1354  	// where we are (current*) vs where we want to fit each side to (inner*)
  1355  	currentTop := obj.TopLeft.Y
  1356  	currentBottom := obj.TopLeft.Y + obj.Height
  1357  	currentLeft := obj.TopLeft.X
  1358  	currentRight := obj.TopLeft.X + obj.Width
  1359  
  1360  	innerTop := math.Inf(1)
  1361  	innerBottom := math.Inf(-1)
  1362  	innerLeft := math.Inf(1)
  1363  	innerRight := math.Inf(-1)
  1364  
  1365  	// we create boxes for our inside label and icon, and will check against overlaps with any internal boxes
  1366  	var labelPosition, iconPosition label.Position
  1367  	var labelBox, iconBox *geo.Box
  1368  	if obj.HasLabel() && obj.LabelPosition != nil {
  1369  		labelPosition = label.FromString(*obj.LabelPosition)
  1370  		switch labelPosition {
  1371  		case label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight,
  1372  			label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight,
  1373  			label.InsideMiddleLeft, label.InsideMiddleRight:
  1374  			labelTL := obj.GetLabelTopLeft()
  1375  			if labelTL != nil {
  1376  				labelBox = geo.NewBox(labelTL, float64(obj.LabelDimensions.Width)+2*label.PADDING, float64(obj.LabelDimensions.Height))
  1377  			}
  1378  		}
  1379  	}
  1380  	if obj.HasIcon() && obj.IconPosition != nil {
  1381  		iconPosition = label.FromString(*obj.IconPosition)
  1382  		switch iconPosition {
  1383  		case label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight,
  1384  			label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight,
  1385  			label.InsideMiddleLeft, label.InsideMiddleRight:
  1386  			iconTL := obj.GetIconTopLeft()
  1387  			if iconTL != nil {
  1388  				iconBox = geo.NewBox(iconTL, d2target.MAX_ICON_SIZE, d2target.MAX_ICON_SIZE)
  1389  			}
  1390  		}
  1391  	}
  1392  
  1393  	// update the inner positions for children's margin and collect the outside boxes that we cannot overlap with
  1394  	var innerBoxes []geo.Box
  1395  	for _, child := range obj.ChildrenArray {
  1396  		margin, _ := child.Spacing()
  1397  		dx, dy := child.GetModifierElementAdjustments()
  1398  
  1399  		if labelBox != nil || iconBox != nil {
  1400  			var childLabelBox *geo.Box
  1401  			var childLabelPosition, childIconPosition label.Position
  1402  			if child.HasLabel() && child.LabelPosition != nil {
  1403  				childLabelPosition = label.FromString(*child.LabelPosition)
  1404  				if childLabelPosition.IsOutside() {
  1405  					childLabelTL := child.GetLabelTopLeft()
  1406  
  1407  					childLabelBox = geo.NewBox(
  1408  						childLabelTL,
  1409  						float64(child.LabelDimensions.Width),
  1410  						float64(child.LabelDimensions.Height),
  1411  					)
  1412  					innerBoxes = append(innerBoxes, *childLabelBox)
  1413  				}
  1414  			}
  1415  			if child.HasIcon() && child.IconPosition != nil {
  1416  				childIconPosition = label.FromString(*child.IconPosition)
  1417  				if childIconPosition.IsOutside() {
  1418  					childIconTL := child.GetIconTopLeft()
  1419  
  1420  					childIconBox := geo.NewBox(childIconTL, d2target.MAX_ICON_SIZE, d2target.MAX_ICON_SIZE)
  1421  					innerBoxes = append(innerBoxes, *childIconBox)
  1422  				}
  1423  			}
  1424  		}
  1425  
  1426  		innerTop = math.Min(innerTop, child.TopLeft.Y-dy-math.Max(margin.Top, padding.Top))
  1427  		innerBottom = math.Max(innerBottom, child.TopLeft.Y+child.Height+math.Max(margin.Bottom, padding.Bottom))
  1428  		innerLeft = math.Min(innerLeft, child.TopLeft.X-math.Max(margin.Left, padding.Left))
  1429  		innerRight = math.Max(innerRight, child.TopLeft.X+child.Width+dx+math.Max(margin.Right, padding.Right))
  1430  	}
  1431  
  1432  	// collect edge label boxes and update inner box for internal edges
  1433  	for _, edge := range obj.Graph.Edges {
  1434  		if !edge.Src.IsDescendantOf(obj) || !edge.Dst.IsDescendantOf(obj) {
  1435  			continue
  1436  		}
  1437  		// check internal edge + their labels
  1438  		if edge.Label.Value != "" {
  1439  			labelPosition := label.InsideMiddleCenter
  1440  			if edge.LabelPosition != nil {
  1441  				labelPosition = label.FromString(*edge.LabelPosition)
  1442  			}
  1443  			labelWidth := float64(edge.LabelDimensions.Width)
  1444  			labelHeight := float64(edge.LabelDimensions.Height)
  1445  			point, _ := labelPosition.GetPointOnRoute(edge.Route, 2, 0, labelWidth, labelHeight)
  1446  
  1447  			if labelBox != nil || iconBox != nil {
  1448  				innerBoxes = append(innerBoxes, geo.Box{TopLeft: point, Width: labelWidth, Height: labelHeight})
  1449  			}
  1450  
  1451  			innerTop = math.Min(innerTop, point.Y-padding.Top)
  1452  			innerBottom = math.Max(innerBottom, point.Y+labelHeight+padding.Bottom)
  1453  			innerLeft = math.Min(innerLeft, point.X-padding.Left)
  1454  			innerRight = math.Max(innerRight, point.X+labelWidth+padding.Right)
  1455  		}
  1456  		for _, point := range edge.Route {
  1457  			innerTop = math.Min(innerTop, point.Y-padding.Top)
  1458  			innerBottom = math.Max(innerBottom, point.Y+padding.Bottom)
  1459  			innerLeft = math.Min(innerLeft, point.X-padding.Left)
  1460  			innerRight = math.Max(innerRight, point.X+padding.Right)
  1461  		}
  1462  	}
  1463  
  1464  	// how much do we need to shrink each side
  1465  	topDelta := innerTop - currentTop
  1466  	bottomDelta := currentBottom - innerBottom
  1467  	leftDelta := innerLeft - currentLeft
  1468  	rightDelta := currentRight - innerRight
  1469  
  1470  	if topDelta > 0 || bottomDelta > 0 || leftDelta > 0 || rightDelta > 0 {
  1471  		var leftOverlap, rightOverlap, topOverlap, bottomOverlap float64
  1472  		var labelSide, iconSide geo.Orientation
  1473  		if labelBox != nil {
  1474  			switch labelPosition {
  1475  			case label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight:
  1476  				labelSide = geo.Top
  1477  			case label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight:
  1478  				labelSide = geo.Bottom
  1479  			case label.InsideMiddleLeft:
  1480  				labelSide = geo.Left
  1481  			case label.InsideMiddleRight:
  1482  				labelSide = geo.Right
  1483  			default:
  1484  				labelSide = geo.NONE
  1485  			}
  1486  			// move labelBox to its position with the merged delta and check for overlaps
  1487  			switch labelSide {
  1488  			case geo.Top:
  1489  				if topDelta > 0 {
  1490  					labelBox.TopLeft.Y += topDelta
  1491  				}
  1492  			case geo.Bottom:
  1493  				if bottomDelta > 0 {
  1494  					labelBox.TopLeft.Y -= bottomDelta
  1495  				}
  1496  			case geo.Left:
  1497  				if leftDelta > 0 {
  1498  					labelBox.TopLeft.X += leftDelta
  1499  				}
  1500  			case geo.Right:
  1501  				if rightDelta > 0 {
  1502  					labelBox.TopLeft.X -= rightDelta
  1503  				}
  1504  			}
  1505  			switch labelSide {
  1506  			case geo.Top:
  1507  				if topDelta > 0 {
  1508  					for _, box := range innerBoxes {
  1509  						if labelBox.Overlaps(box) {
  1510  							dy := labelBox.TopLeft.Y + labelBox.Height - box.TopLeft.Y
  1511  							topOverlap = go2.Max(topOverlap, dy)
  1512  						}
  1513  					}
  1514  				}
  1515  			case geo.Bottom:
  1516  				if bottomDelta > 0 {
  1517  					for _, box := range innerBoxes {
  1518  						if labelBox.Overlaps(box) {
  1519  							dy := box.TopLeft.Y + box.Height - labelBox.TopLeft.Y
  1520  							bottomOverlap = go2.Max(bottomOverlap, dy)
  1521  						}
  1522  					}
  1523  				}
  1524  			case geo.Left:
  1525  				if leftDelta > 0 {
  1526  					for _, box := range innerBoxes {
  1527  						if labelBox.Overlaps(box) {
  1528  							dx := labelBox.TopLeft.X + labelBox.Width - box.TopLeft.X
  1529  							leftOverlap = go2.Max(leftOverlap, dx)
  1530  						}
  1531  					}
  1532  				}
  1533  			case geo.Right:
  1534  				if rightDelta > 0 {
  1535  					for _, box := range innerBoxes {
  1536  						if labelBox.Overlaps(box) {
  1537  							dx := box.TopLeft.X + box.Width - labelBox.TopLeft.X
  1538  							rightOverlap = go2.Max(rightOverlap, dx)
  1539  						}
  1540  					}
  1541  				}
  1542  			}
  1543  		}
  1544  		if iconBox != nil {
  1545  			switch iconPosition {
  1546  			case label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight:
  1547  				iconSide = geo.Top
  1548  			case label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight:
  1549  				iconSide = geo.Bottom
  1550  			case label.InsideMiddleLeft:
  1551  				iconSide = geo.Left
  1552  			case label.InsideMiddleRight:
  1553  				iconSide = geo.Right
  1554  			default:
  1555  				iconSide = geo.NONE
  1556  			}
  1557  			// move iconBox to its position with the merged delta and check for overlaps
  1558  			switch iconSide {
  1559  			case geo.Top:
  1560  				if topDelta > 0 {
  1561  					iconBox.TopLeft.Y += topDelta
  1562  				}
  1563  			case geo.Bottom:
  1564  				if bottomDelta > 0 {
  1565  					iconBox.TopLeft.Y -= bottomDelta
  1566  				}
  1567  			case geo.Left:
  1568  				if leftDelta > 0 {
  1569  					iconBox.TopLeft.X += leftDelta
  1570  				}
  1571  			case geo.Right:
  1572  				if rightDelta > 0 {
  1573  					iconBox.TopLeft.X -= rightDelta
  1574  				}
  1575  			}
  1576  			switch iconSide {
  1577  			case geo.Top:
  1578  				if topDelta > 0 {
  1579  					for _, box := range innerBoxes {
  1580  						if iconBox.Overlaps(box) {
  1581  							dy := iconBox.TopLeft.Y + iconBox.Height - box.TopLeft.Y
  1582  							topOverlap = go2.Max(topOverlap, dy)
  1583  						}
  1584  					}
  1585  				}
  1586  			case geo.Bottom:
  1587  				if bottomDelta > 0 {
  1588  					for _, box := range innerBoxes {
  1589  						if iconBox.Overlaps(box) {
  1590  							dy := box.TopLeft.Y + box.Height - iconBox.TopLeft.Y
  1591  							bottomOverlap = go2.Max(bottomOverlap, dy)
  1592  						}
  1593  					}
  1594  				}
  1595  			case geo.Left:
  1596  				if leftDelta > 0 {
  1597  					for _, box := range innerBoxes {
  1598  						if iconBox.Overlaps(box) {
  1599  							dx := iconBox.TopLeft.X + iconBox.Width - box.TopLeft.X
  1600  							leftOverlap = go2.Max(leftOverlap, dx)
  1601  						}
  1602  					}
  1603  				}
  1604  			case geo.Right:
  1605  				if rightDelta > 0 {
  1606  					for _, box := range innerBoxes {
  1607  						if iconBox.Overlaps(box) {
  1608  							dx := box.TopLeft.X + box.Width - iconBox.TopLeft.X
  1609  							rightOverlap = go2.Max(rightOverlap, dx)
  1610  						}
  1611  					}
  1612  				}
  1613  			}
  1614  		}
  1615  
  1616  		if leftOverlap > 0 {
  1617  			leftDelta -= leftOverlap + MIN_SPACING
  1618  		}
  1619  		if rightOverlap > 0 {
  1620  			rightDelta -= rightOverlap + MIN_SPACING
  1621  		}
  1622  		if topOverlap > 0 {
  1623  			topDelta -= topOverlap + MIN_SPACING
  1624  		}
  1625  		if bottomOverlap > 0 {
  1626  			bottomDelta -= bottomOverlap + MIN_SPACING
  1627  		}
  1628  	}
  1629  
  1630  	if 0 < topDelta {
  1631  		topDelta = adjustDeltaForEdges(obj, currentTop, topDelta, false)
  1632  		if 0 < topDelta {
  1633  			adjustEdges(obj, currentTop, topDelta, false)
  1634  			obj.TopLeft.Y += topDelta
  1635  			obj.Height -= topDelta
  1636  		}
  1637  	}
  1638  	if 0 < bottomDelta {
  1639  		bottomDelta = adjustDeltaForEdges(obj, currentBottom, -bottomDelta, false)
  1640  		if 0 < bottomDelta {
  1641  			adjustEdges(obj, currentBottom, -bottomDelta, false)
  1642  			obj.Height -= bottomDelta
  1643  		}
  1644  	}
  1645  	if 0 < leftDelta {
  1646  		leftDelta = adjustDeltaForEdges(obj, currentLeft, leftDelta, true)
  1647  		if 0 < leftDelta {
  1648  			adjustEdges(obj, currentLeft, leftDelta, true)
  1649  			obj.TopLeft.X += leftDelta
  1650  			obj.Width -= leftDelta
  1651  		}
  1652  	}
  1653  	if 0 < rightDelta {
  1654  		rightDelta = adjustDeltaForEdges(obj, currentRight, -rightDelta, true)
  1655  		if 0 < rightDelta {
  1656  			adjustEdges(obj, currentRight, -rightDelta, true)
  1657  			obj.Width -= rightDelta
  1658  		}
  1659  	}
  1660  }
  1661  
  1662  func adjustDeltaForEdges(obj *d2graph.Object, objPosition, delta float64, isHorizontal bool) (newMagnitude float64) {
  1663  	isOnCollapsingSide := func(p *geo.Point) bool {
  1664  		var position float64
  1665  		if isHorizontal {
  1666  			position = p.X
  1667  		} else {
  1668  			position = p.Y
  1669  		}
  1670  		if geo.PrecisionCompare(position, objPosition, 1) == 0 {
  1671  			return false
  1672  		}
  1673  		// check for edges on side corners
  1674  		var isOnSide bool
  1675  		if isHorizontal {
  1676  			if geo.PrecisionCompare(p.Y, obj.TopLeft.Y, 1) == 0 ||
  1677  				geo.PrecisionCompare(p.Y, obj.TopLeft.Y+obj.Height, 1) == 0 {
  1678  				isOnSide = true
  1679  			}
  1680  		} else {
  1681  			if geo.PrecisionCompare(p.X, obj.TopLeft.X, 1) == 0 ||
  1682  				geo.PrecisionCompare(p.X, obj.TopLeft.X+obj.Width, 1) == 0 {
  1683  				isOnSide = true
  1684  			}
  1685  		}
  1686  		if !isOnSide {
  1687  			return false
  1688  		}
  1689  		buffer := MIN_SPACING
  1690  		var isInRange bool
  1691  		if delta > 0 {
  1692  			if objPosition <= position && position <= objPosition+delta+buffer {
  1693  				isInRange = true
  1694  			}
  1695  		} else {
  1696  			if objPosition+delta-buffer <= position && position <= objPosition {
  1697  				isInRange = true
  1698  			}
  1699  		}
  1700  		return isInRange
  1701  	}
  1702  	hasEdgeOnCollapsingSide := false
  1703  	outermost := objPosition + delta
  1704  	for _, edge := range obj.Graph.Edges {
  1705  		if edge.Src == obj {
  1706  			p := edge.Route[0]
  1707  			if isOnCollapsingSide(p) {
  1708  				hasEdgeOnCollapsingSide = true
  1709  				var position float64
  1710  				if isHorizontal {
  1711  					position = p.X
  1712  				} else {
  1713  					position = p.Y
  1714  				}
  1715  				if delta < 0 {
  1716  					outermost = math.Max(outermost, position)
  1717  				} else {
  1718  					outermost = math.Min(outermost, position)
  1719  				}
  1720  			}
  1721  		}
  1722  		if edge.Dst == obj {
  1723  			p := edge.Route[len(edge.Route)-1]
  1724  			if isOnCollapsingSide(p) {
  1725  				hasEdgeOnCollapsingSide = true
  1726  				var position float64
  1727  				if isHorizontal {
  1728  					position = p.X
  1729  				} else {
  1730  					position = p.Y
  1731  				}
  1732  				if delta < 0 {
  1733  					outermost = math.Max(outermost, position)
  1734  				} else {
  1735  					outermost = math.Min(outermost, position)
  1736  				}
  1737  			}
  1738  		}
  1739  	}
  1740  	newMagnitude = math.Abs(delta)
  1741  	if hasEdgeOnCollapsingSide {
  1742  		// only reduce to outermost + DEFAULT_PADDING
  1743  		if delta < 0 {
  1744  			newMagnitude = math.Max(0, objPosition-(outermost+DEFAULT_PADDING))
  1745  		} else {
  1746  			newMagnitude = math.Max(0, (outermost-DEFAULT_PADDING)-objPosition)
  1747  		}
  1748  	}
  1749  	return newMagnitude
  1750  }
  1751  
  1752  func adjustEdges(obj *d2graph.Object, objPosition, delta float64, isHorizontal bool) {
  1753  	adjust := func(p *geo.Point) {
  1754  		var position float64
  1755  		if isHorizontal {
  1756  			position = p.X
  1757  		} else {
  1758  			position = p.Y
  1759  		}
  1760  		if geo.PrecisionCompare(position, objPosition, 1) == 0 {
  1761  			if isHorizontal {
  1762  				p.X += delta
  1763  			} else {
  1764  				p.Y += delta
  1765  			}
  1766  		} else {
  1767  			// check side corners
  1768  			var isOnSide bool
  1769  			if isHorizontal {
  1770  				if geo.PrecisionCompare(p.Y, obj.TopLeft.Y, 1) == 0 ||
  1771  					geo.PrecisionCompare(p.Y, obj.TopLeft.Y+obj.Height, 1) == 0 {
  1772  					isOnSide = true
  1773  				}
  1774  			} else {
  1775  				if geo.PrecisionCompare(p.X, obj.TopLeft.X, 1) == 0 ||
  1776  					geo.PrecisionCompare(p.X, obj.TopLeft.X+obj.Width, 1) == 0 {
  1777  					isOnSide = true
  1778  				}
  1779  			}
  1780  			if isOnSide {
  1781  				var isInRange bool
  1782  				if delta > 0 {
  1783  					if objPosition < position && position < objPosition+delta {
  1784  						isInRange = true
  1785  					}
  1786  				} else {
  1787  					if objPosition+delta < position && position < objPosition {
  1788  						isInRange = true
  1789  					}
  1790  				}
  1791  				if isInRange {
  1792  					if isHorizontal {
  1793  						p.X = objPosition + delta
  1794  					} else {
  1795  						p.Y = objPosition + delta
  1796  					}
  1797  				}
  1798  			}
  1799  		}
  1800  	}
  1801  
  1802  	for _, edge := range obj.Graph.Edges {
  1803  		if edge.Src == obj {
  1804  			adjust(edge.Route[0])
  1805  		}
  1806  		if edge.Dst == obj {
  1807  			adjust(edge.Route[len(edge.Route)-1])
  1808  		}
  1809  	}
  1810  }
  1811  

View as plain text