package d2dagrelayout

import (
	
	
	
	
	

	

	

	
	
	
	
	
	
	
)

const (
	MIN_RANK_SEP    = 60
	EDGE_LABEL_GAP  = 20
	DEFAULT_PADDING = 30.
	MIN_SPACING     = 10.
)

type ConfigurableOpts struct {
	NodeSep int `json:"nodesep"`
	EdgeSep int `json:"edgesep"`
}

var DefaultOpts = ConfigurableOpts{
	NodeSep: 60,
	EdgeSep: 20,
}

type dagreOpts struct {
	// for a top to bottom graph: ranksep is y spacing, nodesep is x spacing, edgesep is x spacing
	ranksep int
	// graph direction: tb (top to bottom)| bt | lr | rl
	rankdir string

	ConfigurableOpts
}

func ( context.Context,  *d2graph.Graph) ( error) {
	return Layout(, , nil)
}

func ( context.Context,  *d2graph.Graph,  *ConfigurableOpts) ( error) {
	if  == nil {
		 = context.Background()
	}
	if  == nil {
		 = &DefaultOpts
	}
	defer xdefer.Errorf(&, "failed to dagre layout")
	if  := layoutguard.CheckGraph(, "dagre", );  != nil {
		return 
	}

	 := dagreOpts{
		ConfigurableOpts: ConfigurableOpts{
			EdgeSep: .EdgeSep,
			NodeSep: .NodeSep,
		},
	}
	 := false
	switch .Root.Direction.Value {
	case "down":
		.rankdir = "TB"
	case "right":
		.rankdir = "LR"
		 = true
	case "left":
		.rankdir = "RL"
		 = true
	case "up":
		.rankdir = "BT"
	default:
		.rankdir = "TB"
	}

	// set label and icon positions for dagre
	for ,  := range .Objects {
		positionLabelsIcons()
	}

	 := 0
	 := 0
	for ,  := range .Edges {
		 := .LabelDimensions.Width
		 := .LabelDimensions.Height
		 = go2.Max(, )
		 = go2.Max(, )
	}

	if ! {
		.ranksep = go2.Max(100, +40)
	} else {
		.ranksep = go2.Max(100, +40)
		// use existing config
		// rootAttrs.NodeSep = rootAttrs.EdgeSep
		// // configure vertical padding
		// rootAttrs.EdgeSep = maxLabelHeight + 40
		// Note: non-containers have both of these as padding (rootAttrs.NodeSep + rootAttrs.EdgeSep)
	}

	 := NewObjectMapper()
	for ,  := range .Objects {
		.Register()
	}
	 := newEndpointResolver()
	type  struct {
		,  *d2graph.Object
	}
	 := make(map[*d2graph.Edge], len(.Edges))
	 := make(map[]int, len(.Edges))
	for ,  := range .Edges {
		,  := .resolve()
		 := {: , : }
		[] = 
		[]++
	}

	 := dagro.NewGraph(dagro.GraphOptions{Compound: true, Multigraph: true}).SetGraph(dagro.Attrs{
		"ranksep": float64(.ranksep),
		"edgesep": float64(.EdgeSep),
		"nodesep": float64(.NodeSep),
		"rankdir": .rankdir,
	})
	for ,  := range .Objects {
		 := .ToID()
		.SetNode(, dagro.Attrs{
			"id":     ,
			"width":  float64(int(.Width)),
			"height": float64(int(.Height)),
		})
		if .Parent != .Root {
			if  := .SetParent(, .ToID(.Parent));  != nil {
				return 
			}
		}
	}

	for ,  := range .Edges {
		 := []
		,  := ., .

		 := .LabelDimensions.Width
		 := .LabelDimensions.Height

		 := []
		if  !=  {
			 += [{: , : }]
		}

		// We want to leave some gap between multiple edges
		if  > 1 {
			switch .Root.Direction.Value {
			case "down", "up", "":
				 += EDGE_LABEL_GAP
			case "left", "right":
				 += EDGE_LABEL_GAP
			}
		}

		.SetEdge(
			.ToID(),
			.ToID(),
			dagro.Attrs{
				"width":    float64(),
				"height":   float64(),
				"labelpos": "c",
			},
			.AbsID(),
		)
	}

	if  := .Err();  != nil {
		return 
	}
	// dagro does not accept a context. Check immediately around the call; the
	// topology preflight above bounds inputs before entering this section.
	if  := dagro.Layout();  != nil {
		return 
	}
	if  := .Err();  != nil {
		return 
	}

	for ,  := range .Nodes() {
		,  := .Node().(dagro.Attrs)
		if ! {
			return fmt.Errorf("dagro returned invalid node label for %q", )
		}
		,  := ["id"].(string)
		if ! {
			return fmt.Errorf("dagro returned node %q without an id", )
		}
		 := .ToObj()
		if  == nil {
			return fmt.Errorf("dagro returned unknown node id %q", )
		}
		,  := ["x"].(float64)
		,  := ["y"].(float64)
		,  := ["width"].(float64)
		,  := ["height"].(float64)
		if ! || ! || ! || ! {
			return fmt.Errorf("dagro returned invalid geometry for node %q", )
		}

		// dagre gives center of node
		.TopLeft = geo.NewPoint(math.Round(-/2), math.Round(-/2))
		.Width = math.Ceil()
		.Height = math.Ceil()
	}

	 := .Edges()
	if len() != len(.Edges) {
		return fmt.Errorf("dagro returned %d edges, expected %d", len(), len(.Edges))
	}
	for ,  := range .Edges {
		,  := .Edge([]).(dagro.Attrs)
		if ! {
			return fmt.Errorf("dagro returned invalid edge label for %q", [].Name)
		}
		,  := ["points"].([]dagro.Point)
		if ! {
			return fmt.Errorf("dagro returned edge %q without points", [].Name)
		}

		 := make([]*geo.Point, len())
		for ,  := range  {
			 := geo.NewPoint(.X, .Y)
			if .SrcArrow && !.DstArrow {
				[len()--1] = 
			} else {
				[] = 
			}
		}
		// Dagre 3.1 self-loop routes contain repeated control points. Remove only
		// consecutive duplicates so downstream tangent calculations never see a
		// zero-length segment.
		 = deduplicateRoutePoints()
		if .Src == .Dst {
			// The self-loop controls describe the loop outside the node, but do not
			// include usable node-facing endpoints. Center sentinels give
			// TraceToShape a direction from which to chop the route to each border.
			 := .Src.Center()
			 = append([]*geo.Point{.Copy()}, ...)
			 = append(, .Copy())
		}
		if len() < 2 {
			return fmt.Errorf("dagro returned edge %q without a usable route", [].Name)
		}

		,  := 0, len()-1
		,  := [], []

		// chop where edge crosses the source/target boxes since container edges were routed to a descendant
		if .Src != .Dst {
			for  := 1;  < len(); ++ {
				 := *geo.NewSegment([-1], [])
				if  := .Src.Box.Intersections(); len() > 0 {
					 = [0]
					 =  - 1
				}

				if  := .Dst.Box.Intersections(); len() > 0 {
					 = [0]
					 = 
					break
				}
			}
		}
		 = [ : +1]
		[0] = 
		[len()-1] = 

		.Route = 
	}

	adjustRankSpacing(, float64(.ranksep), )
	adjustCrossRankSpacing(, float64(.ranksep), !)
	fitContainerPadding(, float64(.ranksep), )

	for ,  := range .Edges {
		 := .Route
		,  := 0, len()-1
		,  := [], []

		// arrowheads can appear broken if segments are very short from dagre routing a point just outside the shape
		// to fix this, we try extending the previous segment into the shape instead of having a very short segment
		if +2 < len() {
			 := *geo.NewSegment(, [+1])
			if .Length() < d2graph.MIN_SEGMENT_LEN {
				// we don't want a very short segment right next to the source because it will mess up the arrowhead
				// instead we want to extend the next segment into the shape border if possible
				 := [+1]
				 := [+2]

				// Note: in other direction to extend towards source
				 := *geo.NewSegment(, )
				 := .ToVector()
				 := .ToVector().Add(.AddLength(d2graph.MIN_SEGMENT_LEN)).ToPoint()
				 := *geo.NewSegment(, )

				if  := .Src.Box.Intersections(); len() > 0 {
					++
					[] = [0]
					 = []
				}
			}
		}
		if -2 >= 0 {
			 := *geo.NewSegment(, [-1])
			if .Length() < d2graph.MIN_SEGMENT_LEN {
				// extend the prev segment into the shape border if possible
				 := [-2]
				 := [-1]

				 := *geo.NewSegment(, )
				 := .ToVector()
				 := .ToVector().Add(.AddLength(d2graph.MIN_SEGMENT_LEN)).ToPoint()
				 := *geo.NewSegment(, )

				if  := .Dst.Box.Intersections(); len() > 0 {
					--
					[] = [0]
					 = []
				}
			}
		}

		var ,  *geo.Point
		// if the edge passes through 3d/multiple, use the offset box for tracing to border
		if ,  := .Src.GetModifierElementAdjustments();  != 0 ||  != 0 {
			if .X > .Src.TopLeft.X+ &&
				.Y < .Src.TopLeft.Y+.Src.Height- {
				 = .Src.TopLeft.Copy()
				.Src.TopLeft.X += 
				.Src.TopLeft.Y -= 
			}
		}
		if ,  := .Dst.GetModifierElementAdjustments();  != 0 ||  != 0 {
			if .X > .Dst.TopLeft.X+ &&
				.Y < .Dst.TopLeft.Y+.Dst.Height- {
				 = .Dst.TopLeft.Copy()
				.Dst.TopLeft.X += 
				.Dst.TopLeft.Y -= 
			}
		}

		,  = .TraceToShape(, , )
		 = [ : +1]

		// build a curved path from the dagre route
		 := make([]geo.Vector, 0, len()-1)
		for  := 1;  < len(); ++ {
			 = append(, [-1].VectorTo([]))
		}

		 := make([]*geo.Point, 0)
		 = append(, [0])
		if len() > 1 {
			 = append(, [0].AddVector([0].Multiply(.8)))
			for  := 1;  < len()-2; ++ {
				 := []
				 := []
				 = append(, .AddVector(.Multiply(.2)))
				 = append(, .AddVector(.Multiply(.5)))
				 = append(, .AddVector(.Multiply(.8)))
			}
			 = append(, [len()-2].AddVector([len()-1].Multiply(.2)))
			.IsCurve = true
		}
		 = append(, [len()-1])

		.Route = 
		// compile needs to assign edge label positions
		if .Label.Value != "" {
			.LabelPosition = go2.Pointer(label.InsideMiddleCenter.String())
		}

		// undo 3d/multiple offset
		if  != nil {
			.Src.TopLeft.X = .X
			.Src.TopLeft.Y = .Y
		}
		if  != nil {
			.Dst.TopLeft.X = .X
			.Dst.TopLeft.Y = .Y
		}
	}

	return nil
}

func deduplicateRoutePoints( []*geo.Point) []*geo.Point {
	if len() < 2 {
		return 
	}
	 := [:1]
	for ,  := range [1:] {
		if !.Equals([len()-1]) {
			 = append(, )
		}
	}
	return 
}

type containerEndpoints struct {
	head, tail *d2graph.Object
}

type endpointResolver struct {
	g          *d2graph.Graph
	containers map[*d2graph.Object]containerEndpoints
}

func newEndpointResolver( *d2graph.Graph) *endpointResolver {
	return &endpointResolver{
		g:          ,
		containers: make(map[*d2graph.Object]containerEndpoints),
	}
}

func ( *endpointResolver) ( *d2graph.Object) *d2graph.Object {
	return .endpoints().head
}

func ( *endpointResolver) ( *d2graph.Object) *d2graph.Object {
	return .endpoints().tail
}

func ( *endpointResolver) ( *d2graph.Object) containerEndpoints {
	,  := .containers[]
	if ! {
		.head, .tail = getLongestEdgeChainEndpoints(.g, )
		.containers[] = 
	}
	return 
}

func ( *endpointResolver) ( *d2graph.Edge) (*d2graph.Object, *d2graph.Object) {
	// dagre doesn't work with edges to containers so we connect container edges to their first child instead (going all the way down)
	// we will chop the edge where it intersects the container border so it only shows the edge from the container
	 := .Src
	for len(.Children) > 0 && .Class == nil && .SQLTable == nil {
		// We want to get the bottom node of sources, setting its rank higher than all children
		 = .tail()
	}
	 := .Dst
	for len(.Children) > 0 && .Class == nil && .SQLTable == nil {
		 = .head()
	}
	if .SrcArrow && !.DstArrow {
		// for `b <- a`, edge.Edge is `a -> b` and we expect this routing result
		,  = , 
	}
	return , 
}

type containerTopology struct {
	container   *d2graph.Object
	hasIncoming map[*d2graph.Object]bool
	outgoing    map[*d2graph.Object][]*d2graph.Object
}

func newContainerTopology( *d2graph.Graph,  *d2graph.Object) *containerTopology {
	 := &containerTopology{
		container:   ,
		hasIncoming: make(map[*d2graph.Object]bool, len(.ChildrenArray)),
		outgoing:    make(map[*d2graph.Object][]*d2graph.Object, len(.ChildrenArray)+1),
	}
	for ,  := range .Edges {
		 := inContainer(.Src, )
		 := inContainer(.Dst, )
		if  == nil ||  == nil {
			continue
		}

		// The original head test counts every edge from anywhere in the
		// container to a direct child's subtree, including internal edges.
		if  !=  {
			.hasIncoming[] = true
		}

		// Preserve edge order and duplicates: the breadth-first walk's rank
		// updates are order-sensitive even though the graph is usually acyclic.
		if  !=  {
			.outgoing[] = append(.outgoing[], )
		}
		// A container can enter the old traversal when an edge terminates on
		// it. From there, every edge whose source is inside it is reachable.
		if  !=  &&  !=  {
			.outgoing[] = append(.outgoing[], )
		}
	}
	return 
}

func ( *containerTopology) () (*d2graph.Object, *d2graph.Object) {
	 := make(map[*d2graph.Object]int)
	 := make(map[*d2graph.Object]int)

	for ,  := range .container.ChildrenArray {
		if .hasIncoming[] {
			continue
		}
		[] = 1
		[] = 1
		 := []*d2graph.Object{}
		 := make(map[*d2graph.Object]struct{})
		for len() > 0 {
			 := [0]
			 = [1:]
			if ,  := [];  {
				continue
			}
			[] = struct{}{}
			for ,  := range .outgoing[] {
				if []+1 > [] {
					[] = [] + 1
					[] = go2.Max([], [])
				}
				 = append(, )
			}
		}
	}

	 := int(math.MinInt32)
	 := int(math.MinInt32)
	for ,  := range .container.ChildrenArray {
		 = go2.Max(, [])
		 = go2.Max(, [])
	}

	var ,  []*d2graph.Object
	for ,  := range .container.ChildrenArray {
		if [] == 1 && [] ==  {
			 = append(, )
		}
		if [] ==  {
			 = append(, )
		}
	}

	 := .container.ChildrenArray[0]
	if len() > 0 {
		 = [len()/2]
	}
	return , [len()/2]
}

func getLongestEdgeChainEndpoints( *d2graph.Graph,  *d2graph.Object) (*d2graph.Object, *d2graph.Object) {
	return newContainerTopology(, ).longestChainEndpoints()
}

func inContainer(,  *d2graph.Object) *d2graph.Object {
	if  == nil {
		return nil
	}
	if  ==  {
		return 
	}
	if .Parent ==  {
		return 
	}
	return (.Parent, )
}

func positionLabelsIcons( *d2graph.Object) {
	if .Icon != nil && .IconPosition == nil {
		if len(.ChildrenArray) > 0 {
			.IconPosition = go2.Pointer(label.OutsideTopLeft.String())
			if .LabelPosition == nil {
				.LabelPosition = go2.Pointer(label.OutsideTopRight.String())
				return
			}
		} else if .SQLTable != nil || .Class != nil || .Language != "" {
			.IconPosition = go2.Pointer(label.OutsideTopLeft.String())
		} else {
			.IconPosition = go2.Pointer(label.InsideMiddleCenter.String())
		}
	}
	if .HasLabel() && .LabelPosition == nil {
		if len(.ChildrenArray) > 0 {
			.LabelPosition = go2.Pointer(label.OutsideTopCenter.String())
		} else if .HasOutsideBottomLabel() {
			.LabelPosition = go2.Pointer(label.OutsideBottomCenter.String())
		} else if .Icon != nil {
			.LabelPosition = go2.Pointer(label.InsideTopCenter.String())
		} else {
			.LabelPosition = go2.Pointer(label.InsideMiddleCenter.String())
		}
		if float64(.LabelDimensions.Width) > .Width || float64(.LabelDimensions.Height) > .Height {
			if len(.ChildrenArray) > 0 {
				.LabelPosition = go2.Pointer(label.OutsideTopCenter.String())
			} else {
				.LabelPosition = go2.Pointer(label.OutsideBottomCenter.String())
			}
		}
	}
}

func getRanks( *d2graph.Graph,  bool) ( [][]*d2graph.Object, , ,  map[*d2graph.Object]int) {
	 := make(map[float64][]*d2graph.Object)
	for ,  := range .Objects {
		if !.IsContainer() {
			if ! {
				 := math.Ceil(.TopLeft.Y + .Height/2)
				[] = append([], )
			} else {
				 := math.Ceil(.TopLeft.X + .Width/2)
				[] = append([], )
			}
		}
	}

	 := make([]float64, 0, len())
	for  := range  {
		 = append(, )
	}
	sort.Slice(, func(,  int) bool {
		return [] < []
	})

	 = make([][]*d2graph.Object, 0, len())
	 = make(map[*d2graph.Object]int)
	for ,  := range  {
		for ,  := range [] {
			[] = 
		}
		 = append(, [])
	}

	 = make(map[*d2graph.Object]int)
	 = make(map[*d2graph.Object]int)
	for ,  := range .Objects {
		if .IsContainer() {
			continue
		}
		 := []
		// update all ancestor's min/max ranks
		for  := .Parent;  != nil &&  != .Root;  = .Parent {
			if ,  := []; ! ||  <  {
				[] = 
			}
			if ,  := []; ! ||  >  {
				[] = 
			}
		}
	}

	return , , , 
}

// shift everything down by distance if it is at or below start position
func shiftDown( *d2graph.Graph, ,  float64,  bool) {
	if  {
		for ,  := range .Edges {
			,  := .Route[0], .Route[len(.Route)-1]
			if  <= .X {
				 := .X == .Src.TopLeft.X+.Src.Width && .Src.TopLeft.X < 
				if ! {
					// src is not shifting and we are on src so don't shift
					.X += 
				}
			}
			if  <= .X {
				 := .X == .Dst.TopLeft.X+.Dst.Width && .Dst.TopLeft.X < 
				if ! {
					.X += 
				}
			}
			for  := 1;  < len(.Route)-1; ++ {
				 := .Route[]
				if .X <  {
					continue
				}
				.X += 
			}
		}
		for ,  := range .Objects {
			if .TopLeft.X <  {
				continue
			}
			.TopLeft.X += 
		}
	} else {
		for ,  := range .Edges {
			,  := .Route[0], .Route[len(.Route)-1]
			if  <= .Y {
				 := .Y == .Src.TopLeft.Y+.Src.Height && .Src.TopLeft.Y < 
				if ! {
					// src is not shifting and we are on src so don't shift
					.Y += 
				}
			}
			if  <= .Y {
				 := .Y == .Dst.TopLeft.Y+.Dst.Height && .Dst.TopLeft.Y < 
				if ! {
					.Y += 
				}
			}
			for  := 1;  < len(.Route)-1; ++ {
				 := .Route[]
				if .Y <  {
					continue
				}
				.Y += 
			}
		}
		for ,  := range .Objects {
			if .TopLeft.Y <  {
				continue
			}
			.TopLeft.Y += 
		}
	}
}

func shiftUp( *d2graph.Graph, ,  float64,  bool) {
	if  {
		for ,  := range .Edges {
			,  := .Route[0], .Route[len(.Route)-1]
			if .X <=  {
				 := .X == .Src.TopLeft.X &&  < .Src.TopLeft.X+.Src.Width
				if ! {
					// src is not shifting and we are on src so don't shift
					.X -= 
				}
			}
			if .X <=  {
				 := .X == .Dst.TopLeft.X &&  < .Dst.TopLeft.X+.Dst.Width
				if ! {
					.X -= 
				}
			}
			for  := 1;  < len(.Route)-1; ++ {
				 := .Route[]
				if  < .X {
					continue
				}
				.X -= 
			}
		}
		for ,  := range .Objects {
			if  < .TopLeft.X {
				continue
			}
			.TopLeft.X -= 
		}
	} else {
		for ,  := range .Edges {
			,  := .Route[0], .Route[len(.Route)-1]
			if .Y <=  {
				// don't shift first edge point if src is not shifting and we are on src
				 := .Y == .Src.TopLeft.Y &&  < .Src.TopLeft.Y+.Src.Height
				if ! {
					.Y -= 
				}
			}
			if .Y <=  {
				 := .Y == .Dst.TopLeft.Y &&  < .Dst.TopLeft.Y
				if ! {
					.Y -= 
				}
			}
			for  := 1;  < len(.Route)-1; ++ {
				 := .Route[]
				// for _, p := range edge.Route {
				if  < .Y {
					continue
				}
				.Y -= 
			}
		}
		for ,  := range .Objects {
			if  < .TopLeft.Y {
				continue
			}
			.TopLeft.Y -= 
		}
	}
}

type crossRankIndex struct {
	incident map[*d2graph.Object][]*d2graph.Edge
}

func newCrossRankIndex( *d2graph.Graph) *crossRankIndex {
	 := &crossRankIndex{
		incident: make(map[*d2graph.Object][]*d2graph.Edge, len(.Objects)),
	}
	for ,  := range .Edges {
		.incident[.Src] = append(.incident[.Src], )
		if .Dst != .Src {
			.incident[.Dst] = append(.incident[.Dst], )
		}
	}
	return 
}

func shiftReachableDownIndexed( *d2graph.Graph,  *crossRankIndex,  *d2graph.Object, ,  float64, ,  bool) map[*d2graph.Object]struct{} {
	 := []*d2graph.Object{}

	 := make(map[*d2graph.Object]struct{})
	 := make(map[*d2graph.Object]struct{})
	 := make(map[*d2graph.Object]struct{})
	 := make(map[*d2graph.Edge]struct{})
	 := func( *d2graph.Object) {
		if ,  := [];  {
			return
		}
		 = append(, )
	}

	// if object below is within this distance after shifting, also shift it
	 := 100.
	 := func( *d2graph.Object) {
		 := .TopLeft.Y + .Height
		 := .TopLeft.X + .Width
		if  {
			 := 
			if ,  := [];  {
				 -= 
			}
			for ,  := range .Objects {
				if  ==  || .IsDescendantOf() {
					continue
				}
				if  < .TopLeft.X &&
					.TopLeft.X < ++ &&
					.TopLeft.Y < .TopLeft.Y+.Height &&
					.TopLeft.Y <  {
					()
				}
			}
		} else {
			 := 
			if ,  := [];  {
				 -= 
			}
			for ,  := range .Objects {
				if  ==  || .IsDescendantOf() {
					continue
				}
				if  < .TopLeft.Y &&
					.TopLeft.Y < ++ &&
					.TopLeft.X < .TopLeft.X+.Width &&
					.TopLeft.X <  {
					()
				}
			}
		}
	}

	 := func() {
		for len() > 0 {
			 := [0]
			 = [1:]
			if ,  := [];  {
				continue
			}
			// skip other objects behind start
			if  !=  {
				if ,  := []; ! {
					if  {
						if .TopLeft.X <  {
							continue
						}
					} else {
						if .TopLeft.Y <  {
							continue
						}
					}
				}
			}

			if  {
				,  := []
				if ! {
					if ! {
						 =  < .TopLeft.X
					} else {
						 =  <= .TopLeft.X
					}
				}

				if  {
					.TopLeft.X += 
					[] = struct{}{}
				}
			} else {
				,  := []
				if ! {
					if ! {
						 =  < .TopLeft.Y
					} else {
						 =  <= .TopLeft.Y
					}
				}
				if  {
					.TopLeft.Y += 
					[] = struct{}{}
				}
			}
			[] = struct{}{}

			if .Parent != .Root && !.IsDescendantOf() {
				(.Parent)
			}

			for ,  := range .ChildrenArray {
				()
			}

			for ,  := range .incident[] {
				if ,  := [];  {
					continue
				}
				if .Src ==  && .Dst ==  {
					if  {
						for ,  := range .Route {
							.X += 
						}
					} else {
						for ,  := range .Route {
							.Y += 
						}
					}
					[] = struct{}{}
					continue
				} else if .Src ==  {
					 := .Route[len(.Route)-1]
					if  {
						if  <= .X &&
							.Dst.TopLeft.X+.Dst.Width < .X+ {
							[.Dst] = struct{}{}
						}
					} else {
						if  <= .Y &&
							.Dst.TopLeft.Y+.Dst.Height < .Y+ {
							[.Dst] = struct{}{}
						}
					}
					(.Dst)
					 := .Route[0]
					 := 0
					,  := []
					if  {
						if  && .X < .TopLeft.X && .X <  {
							.X += 
							++
						}
						for  := ;  < len(.Route); ++ {
							 := .Route[]
							if  <= .X {
								.X += 
							}
						}
					} else {
						if  && .Y < .TopLeft.Y && .Y <  {
							.Y += 
							++
						}
						for  := ;  < len(.Route); ++ {
							 := .Route[]
							if  <= .Y {
								.Y += 
							}
						}
					}
					[] = struct{}{}
				} else if .Dst ==  {
					 := .Route[0]
					if  {
						if  <= .X &&
							.Src.TopLeft.X+.Src.Width < .X+ {
							[.Src] = struct{}{}
						}
					} else {
						if  <= .Y &&
							.Src.TopLeft.Y+.Src.Height < .Y+ {
							[.Src] = struct{}{}
						}
					}
					(.Src)
					 := .Route[len(.Route)-1]
					 := len(.Route)
					,  := []
					if  {
						if  && .X < .TopLeft.X && .X <  {
							.X += 
							--
						}
						for  := 0;  < ; ++ {
							 := .Route[]
							if  <= .X {
								.X += 
							}
						}
					} else {
						if  && .Y < .TopLeft.Y && .Y <  {
							.Y += 
							--
						}
						for  := 0;  < ; ++ {
							 := .Route[]
							if  <= .Y {
								.Y += 
							}
						}
					}
					[] = struct{}{}
				}
			}

			// check for nodes below that need to move from the shift
			()
		}
	}

	()

	 := make(map[*d2graph.Object]struct{})
	for  := range  {
		if .Parent == .Root {
			continue
		}
		if ,  := [.Parent];  {
			continue
		}
		if ,  := [.Parent];  {
			continue
		}

		for  := .Parent;  != .Root;  = .Parent {
			if ,  := [];  {
				break
			}
			if ,  := [];  {
				break
			}

			if  {
				if .TopLeft.X <  {
					.Width += 
					[] = struct{}{}

					()
					()
				}
			} else {
				if .TopLeft.Y <  {
					.Height += 
					[] = struct{}{}

					()
					()
				}
			}
		}
	}

	 := make(map[*d2graph.Object]struct{})
	 := make([]*d2graph.Object, 0, len())
	for  := range  {
		 = append(, )
	}
	for  := range  {
		 = append(, )
	}
	for ,  := range  {
		 := true
		// check if any other shifted is directly above
		for ,  := range  {
			if  ==  {
				continue
			}
			if  {
				if .TopLeft.Y+.Height < .TopLeft.Y ||
					.TopLeft.Y+.Height < .TopLeft.Y {
					// doesn't line up vertically
					continue
				}

				// above and within threshold
				if .TopLeft.X < .TopLeft.X &&
					.TopLeft.X < .TopLeft.X+.Width+ {
					 = false
					break
				}
			} else {
				if .TopLeft.X+.Width < .TopLeft.X ||
					.TopLeft.X+.Width < .TopLeft.X {
					// doesn't line up horizontally
					continue
				}

				// above and within threshold
				if .TopLeft.Y < .TopLeft.Y &&
					.TopLeft.Y < .TopLeft.Y+.Height+ {
					 = false
					break
				}
			}
		}
		if  {
			[] = struct{}{}
		}
	}

	return 
}

func adjustRankSpacing( *d2graph.Graph,  float64,  bool) {
	, , ,  := getRanks(, )

	// shifting bottom rank down first, then moving up to next rank
	for  := len() - 1;  >= 0; -- {
		var  []*d2graph.Object
		var  []*d2graph.Object
		for ,  := range [] {
			if .Parent == .Root {
				continue
			}
			if ,  := [.Parent];  &&  ==  {
				 = append(, .Parent)
			}
			if ,  := [.Parent];  &&  ==  {
				 = append(, .Parent)
			}
		}

		 := make(map[*d2graph.Object]float64)
		for len() > 0 {
			var  []*d2graph.Object
			for ,  := range  {
				,  := .Spacing()
				if ,  := []; ! {
					[] = math.Inf(1)
				}
				var  float64
				if  {
					 := math.Max(0, .Left-/2)
					 = .TopLeft.X - 
				} else {
					 := math.Max(0, .Top-/2)
					 = .TopLeft.Y - 
				}
				[] = math.Min([], )
				for ,  := range .ChildrenArray {
					if ,  := [];  {
						if  !=  {
							continue
						}
					} else {
						if [] !=  {
							continue
						}
					}
					,  := .Spacing()
					if  {
						 = .TopLeft.X - .Left - .Left
					} else {
						 = .TopLeft.Y - .Top - .Top
					}
					[] = math.Min([], )
				}
				if .Parent != .Root {
					 = append(, .Parent)
				}
			}
			 = 
		}

		 := make(map[*d2graph.Object]float64)
		for len() > 0 {
			var  []*d2graph.Object
			for ,  := range  {
				,  := .Spacing()
				if ,  := []; ! {
					[] = math.Inf(-1)
				}
				var  float64
				if  {
					 = .TopLeft.X + .Width + .Right - /2.
				} else {
					 = .TopLeft.Y + .Height + .Bottom - /2.
				}

				[] = math.Max([], )
				for ,  := range .ChildrenArray {
					if ,  := [];  {
						if  !=  {
							continue
						}
					} else {
						if [] !=  {
							continue
						}
					}
					,  := .Spacing()

					if  {
						 = .TopLeft.X + .Width + .Right + .Right
					} else {
						 = .TopLeft.Y + .Height + .Bottom + .Bottom
					}
					[] = math.Max([], )
				}
				if .Parent != .Root {
					 = append(, .Parent)
				}
			}
			 = 
		}

		 := make([]*d2graph.Object, 0, len())
		for  := range  {
			 = append(, )
		}
		// adjust starting ancestors top-down
		sort.Slice(, func(,  int) bool {
			 := [[]]
			 := [[]]
			return  < 
		})

		 := make([]*d2graph.Object, 0, len())
		for  := range  {
			 = append(, )
		}

		// adjust ending ancestors bottom-up
		sort.Slice(, func(,  int) bool {
			 := [[]]
			 := [[]]
			return  < 
		})

		for ,  := range  {
			var  float64
			if  {
				 = .TopLeft.X + .Width
			} else {
				 = .TopLeft.Y + .Height
			}
			 := [] - 
			if  > 0 {
				for ,  := range .Objects {
					if !.IsContainer() {
						continue
					}
					 := []
					 := []
					if  <=  &&  <=  {
						if  &&  <= .TopLeft.X+.Width {
							.Width += 
						} else if ! &&
							 <= .TopLeft.Y+.Height {
							.Height += 
						}
					}
				}
				shiftDown(, , , )
			}
		}

		for ,  := range  {
			var  float64
			if  {
				 = .TopLeft.X
			} else {
				 = .TopLeft.Y
			}
			 :=  - []
			if  > 0 {
				for ,  := range .Objects {
					if !.IsContainer() {
						continue
					}
					 := []
					 := []
					if  <=  &&  <=  {
						if  && .TopLeft.X <=  {
							.Width += 
						} else if ! && .TopLeft.Y <=  {
							.Height += 
						}
					}
				}
				shiftUp(, , , )
			}
		}
	}
}

func adjustCrossRankSpacing( *d2graph.Graph,  float64,  bool) {
	 := newCrossRankIndex()
	var , , ,  map[*d2graph.Object]float64
	if  {
		 = make(map[*d2graph.Object]float64)
		 = make(map[*d2graph.Object]float64)
	} else {
		 = make(map[*d2graph.Object]float64)
		 = make(map[*d2graph.Object]float64)
	}
	for ,  := range .Objects {
		if .IsGridDiagram() {
			continue
		}
		,  := .Spacing()
		if ! {
			if ,  := [];  {
				.Bottom -= 
			}
			if .Bottom > 0 {
				 := shiftReachableDownIndexed(, , , .TopLeft.Y+.Height, .Bottom, , true)
				for  := range  {
					[] = math.Max([], .Bottom)
				}
			}
			if .Bottom > 0 {
				shiftReachableDownIndexed(, , , .TopLeft.Y+.Height, .Bottom, , false)
				.Height += .Bottom
			}
			if ,  := [];  {
				.Top -= 
			}
			if .Top > 0 {
				 := shiftReachableDownIndexed(, , , .TopLeft.Y, .Top, , true)
				for  := range  {
					[] = math.Max([], .Top)
				}
			}
			if .Top > 0 {
				shiftReachableDownIndexed(, , , .TopLeft.Y, .Top, , false)
				.Height += .Top
			}
		} else {
			if ,  := [];  {
				.Right -= 
			}
			if .Right > 0 {
				 := shiftReachableDownIndexed(, , , .TopLeft.X+.Width, .Right, , true)
				for  := range  {
					[] = math.Max([], .Right)
				}
			}
			if .Right > 0 {
				shiftReachableDownIndexed(, , , .TopLeft.X+.Width, .Right, , false)
				.Width += .Right
			}
			if ,  := [];  {
				.Left -= 
			}
			if .Left > 0 {
				 := shiftReachableDownIndexed(, , , .TopLeft.X, .Left, , true)
				for  := range  {
					[] = math.Max([], .Left)
				}
			}
			if .Left > 0 {
				shiftReachableDownIndexed(, , , .TopLeft.X, .Left, , false)
				.Width += .Left
			}
		}
	}
}

func fitContainerPadding( *d2graph.Graph,  float64,  bool) {
	for ,  := range .Root.ChildrenArray {
		fitPadding()
	}
}

func fitPadding( *d2graph.Object) {
	 := strings.ToLower(.Shape.Value)
	 := d2target.DSL_SHAPE_TO_SHAPE_TYPE[]
	// Note: there's no shape-specific padding/placement in dagre yet
	if !.IsContainer() ||  != shape.SQUARE_TYPE {
		return
	}
	for ,  := range .ChildrenArray {
		()
	}

	// we will compute a perfectly fit innerBox merging our padding with children's margin,
	// but we need to add padding and margin together if an outside child label will overlap with our inside label
	,  := .Spacing()
	.Top = math.Max(.Top, DEFAULT_PADDING)
	.Bottom = math.Max(.Bottom, DEFAULT_PADDING)
	.Left = math.Max(.Left, DEFAULT_PADDING)
	.Right = math.Max(.Right, DEFAULT_PADDING)

	// where we are (current*) vs where we want to fit each side to (inner*)
	 := .TopLeft.Y
	 := .TopLeft.Y + .Height
	 := .TopLeft.X
	 := .TopLeft.X + .Width

	 := math.Inf(1)
	 := math.Inf(-1)
	 := math.Inf(1)
	 := math.Inf(-1)

	// we create boxes for our inside label and icon, and will check against overlaps with any internal boxes
	var ,  label.Position
	var ,  *geo.Box
	if .HasLabel() && .LabelPosition != nil {
		 = label.FromString(*.LabelPosition)
		switch  {
		case label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight,
			label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight,
			label.InsideMiddleLeft, label.InsideMiddleRight:
			 := .GetLabelTopLeft()
			if  != nil {
				 = geo.NewBox(, float64(.LabelDimensions.Width)+2*label.PADDING, float64(.LabelDimensions.Height))
			}
		}
	}
	if .HasIcon() && .IconPosition != nil {
		 = label.FromString(*.IconPosition)
		switch  {
		case label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight,
			label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight,
			label.InsideMiddleLeft, label.InsideMiddleRight:
			 := .GetIconTopLeft()
			if  != nil {
				 = geo.NewBox(, d2target.MAX_ICON_SIZE, d2target.MAX_ICON_SIZE)
			}
		}
	}

	// update the inner positions for children's margin and collect the outside boxes that we cannot overlap with
	var  []geo.Box
	for ,  := range .ChildrenArray {
		,  := .Spacing()
		,  := .GetModifierElementAdjustments()

		if  != nil ||  != nil {
			var  *geo.Box
			var ,  label.Position
			if .HasLabel() && .LabelPosition != nil {
				 = label.FromString(*.LabelPosition)
				if .IsOutside() {
					 := .GetLabelTopLeft()

					 = geo.NewBox(
						,
						float64(.LabelDimensions.Width),
						float64(.LabelDimensions.Height),
					)
					 = append(, *)
				}
			}
			if .HasIcon() && .IconPosition != nil {
				 = label.FromString(*.IconPosition)
				if .IsOutside() {
					 := .GetIconTopLeft()

					 := geo.NewBox(, d2target.MAX_ICON_SIZE, d2target.MAX_ICON_SIZE)
					 = append(, *)
				}
			}
		}

		 = math.Min(, .TopLeft.Y--math.Max(.Top, .Top))
		 = math.Max(, .TopLeft.Y+.Height+math.Max(.Bottom, .Bottom))
		 = math.Min(, .TopLeft.X-math.Max(.Left, .Left))
		 = math.Max(, .TopLeft.X+.Width++math.Max(.Right, .Right))
	}

	// collect edge label boxes and update inner box for internal edges
	for ,  := range .Graph.Edges {
		if !.Src.IsDescendantOf() || !.Dst.IsDescendantOf() {
			continue
		}
		// check internal edge + their labels
		if .Label.Value != "" {
			 := label.InsideMiddleCenter
			if .LabelPosition != nil {
				 = label.FromString(*.LabelPosition)
			}
			 := float64(.LabelDimensions.Width)
			 := float64(.LabelDimensions.Height)
			,  := .GetPointOnRoute(.Route, 2, 0, , )

			if  != nil ||  != nil {
				 = append(, geo.Box{TopLeft: , Width: , Height: })
			}

			 = math.Min(, .Y-.Top)
			 = math.Max(, .Y++.Bottom)
			 = math.Min(, .X-.Left)
			 = math.Max(, .X++.Right)
		}
		for ,  := range .Route {
			 = math.Min(, .Y-.Top)
			 = math.Max(, .Y+.Bottom)
			 = math.Min(, .X-.Left)
			 = math.Max(, .X+.Right)
		}
	}

	// how much do we need to shrink each side
	 :=  - 
	 :=  - 
	 :=  - 
	 :=  - 

	if  > 0 ||  > 0 ||  > 0 ||  > 0 {
		var , , ,  float64
		var ,  geo.Orientation
		if  != nil {
			switch  {
			case label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight:
				 = geo.Top
			case label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight:
				 = geo.Bottom
			case label.InsideMiddleLeft:
				 = geo.Left
			case label.InsideMiddleRight:
				 = geo.Right
			default:
				 = geo.NONE
			}
			// move labelBox to its position with the merged delta and check for overlaps
			switch  {
			case geo.Top:
				if  > 0 {
					.TopLeft.Y += 
				}
			case geo.Bottom:
				if  > 0 {
					.TopLeft.Y -= 
				}
			case geo.Left:
				if  > 0 {
					.TopLeft.X += 
				}
			case geo.Right:
				if  > 0 {
					.TopLeft.X -= 
				}
			}
			switch  {
			case geo.Top:
				if  > 0 {
					for ,  := range  {
						if .Overlaps() {
							 := .TopLeft.Y + .Height - .TopLeft.Y
							 = go2.Max(, )
						}
					}
				}
			case geo.Bottom:
				if  > 0 {
					for ,  := range  {
						if .Overlaps() {
							 := .TopLeft.Y + .Height - .TopLeft.Y
							 = go2.Max(, )
						}
					}
				}
			case geo.Left:
				if  > 0 {
					for ,  := range  {
						if .Overlaps() {
							 := .TopLeft.X + .Width - .TopLeft.X
							 = go2.Max(, )
						}
					}
				}
			case geo.Right:
				if  > 0 {
					for ,  := range  {
						if .Overlaps() {
							 := .TopLeft.X + .Width - .TopLeft.X
							 = go2.Max(, )
						}
					}
				}
			}
		}
		if  != nil {
			switch  {
			case label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight:
				 = geo.Top
			case label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight:
				 = geo.Bottom
			case label.InsideMiddleLeft:
				 = geo.Left
			case label.InsideMiddleRight:
				 = geo.Right
			default:
				 = geo.NONE
			}
			// move iconBox to its position with the merged delta and check for overlaps
			switch  {
			case geo.Top:
				if  > 0 {
					.TopLeft.Y += 
				}
			case geo.Bottom:
				if  > 0 {
					.TopLeft.Y -= 
				}
			case geo.Left:
				if  > 0 {
					.TopLeft.X += 
				}
			case geo.Right:
				if  > 0 {
					.TopLeft.X -= 
				}
			}
			switch  {
			case geo.Top:
				if  > 0 {
					for ,  := range  {
						if .Overlaps() {
							 := .TopLeft.Y + .Height - .TopLeft.Y
							 = go2.Max(, )
						}
					}
				}
			case geo.Bottom:
				if  > 0 {
					for ,  := range  {
						if .Overlaps() {
							 := .TopLeft.Y + .Height - .TopLeft.Y
							 = go2.Max(, )
						}
					}
				}
			case geo.Left:
				if  > 0 {
					for ,  := range  {
						if .Overlaps() {
							 := .TopLeft.X + .Width - .TopLeft.X
							 = go2.Max(, )
						}
					}
				}
			case geo.Right:
				if  > 0 {
					for ,  := range  {
						if .Overlaps() {
							 := .TopLeft.X + .Width - .TopLeft.X
							 = go2.Max(, )
						}
					}
				}
			}
		}

		if  > 0 {
			 -=  + MIN_SPACING
		}
		if  > 0 {
			 -=  + MIN_SPACING
		}
		if  > 0 {
			 -=  + MIN_SPACING
		}
		if  > 0 {
			 -=  + MIN_SPACING
		}
	}

	if 0 <  {
		 = adjustDeltaForEdges(, , , false)
		if 0 <  {
			adjustEdges(, , , false)
			.TopLeft.Y += 
			.Height -= 
		}
	}
	if 0 <  {
		 = adjustDeltaForEdges(, , -, false)
		if 0 <  {
			adjustEdges(, , -, false)
			.Height -= 
		}
	}
	if 0 <  {
		 = adjustDeltaForEdges(, , , true)
		if 0 <  {
			adjustEdges(, , , true)
			.TopLeft.X += 
			.Width -= 
		}
	}
	if 0 <  {
		 = adjustDeltaForEdges(, , -, true)
		if 0 <  {
			adjustEdges(, , -, true)
			.Width -= 
		}
	}
}

func adjustDeltaForEdges( *d2graph.Object, ,  float64,  bool) ( float64) {
	 := func( *geo.Point) bool {
		var  float64
		if  {
			 = .X
		} else {
			 = .Y
		}
		if geo.PrecisionCompare(, , 1) == 0 {
			return false
		}
		// check for edges on side corners
		var  bool
		if  {
			if geo.PrecisionCompare(.Y, .TopLeft.Y, 1) == 0 ||
				geo.PrecisionCompare(.Y, .TopLeft.Y+.Height, 1) == 0 {
				 = true
			}
		} else {
			if geo.PrecisionCompare(.X, .TopLeft.X, 1) == 0 ||
				geo.PrecisionCompare(.X, .TopLeft.X+.Width, 1) == 0 {
				 = true
			}
		}
		if ! {
			return false
		}
		 := MIN_SPACING
		var  bool
		if  > 0 {
			if  <=  &&  <= ++ {
				 = true
			}
		} else {
			if +- <=  &&  <=  {
				 = true
			}
		}
		return 
	}
	 := false
	 :=  + 
	for ,  := range .Graph.Edges {
		if .Src ==  {
			 := .Route[0]
			if () {
				 = true
				var  float64
				if  {
					 = .X
				} else {
					 = .Y
				}
				if  < 0 {
					 = math.Max(, )
				} else {
					 = math.Min(, )
				}
			}
		}
		if .Dst ==  {
			 := .Route[len(.Route)-1]
			if () {
				 = true
				var  float64
				if  {
					 = .X
				} else {
					 = .Y
				}
				if  < 0 {
					 = math.Max(, )
				} else {
					 = math.Min(, )
				}
			}
		}
	}
	 = math.Abs()
	if  {
		// only reduce to outermost + DEFAULT_PADDING
		if  < 0 {
			 = math.Max(0, -(+DEFAULT_PADDING))
		} else {
			 = math.Max(0, (-DEFAULT_PADDING)-)
		}
	}
	return 
}

func adjustEdges( *d2graph.Object, ,  float64,  bool) {
	 := func( *geo.Point) {
		var  float64
		if  {
			 = .X
		} else {
			 = .Y
		}
		if geo.PrecisionCompare(, , 1) == 0 {
			if  {
				.X += 
			} else {
				.Y += 
			}
		} else {
			// check side corners
			var  bool
			if  {
				if geo.PrecisionCompare(.Y, .TopLeft.Y, 1) == 0 ||
					geo.PrecisionCompare(.Y, .TopLeft.Y+.Height, 1) == 0 {
					 = true
				}
			} else {
				if geo.PrecisionCompare(.X, .TopLeft.X, 1) == 0 ||
					geo.PrecisionCompare(.X, .TopLeft.X+.Width, 1) == 0 {
					 = true
				}
			}
			if  {
				var  bool
				if  > 0 {
					if  <  &&  < + {
						 = true
					}
				} else {
					if + <  &&  <  {
						 = true
					}
				}
				if  {
					if  {
						.X =  + 
					} else {
						.Y =  + 
					}
				}
			}
		}
	}

	for ,  := range .Graph.Edges {
		if .Src ==  {
			(.Route[0])
		}
		if .Dst ==  {
			(.Route[len(.Route)-1])
		}
	}
}