package d2layouts

import (
	
	
	
	
	
	

	
	
	
	
	
	
	
	
)

type DiagramType string

// a grid diagram at a constant near is
const (
	DefaultGraphType  DiagramType = ""
	ConstantNearGraph DiagramType = "constant-near"
	GridDiagram       DiagramType = "grid-diagram"
	SequenceDiagram   DiagramType = "sequence-diagram"
)

type GraphInfo struct {
	IsConstantNear bool
	DiagramType    DiagramType
}

func ( GraphInfo) () bool {
	return !.IsConstantNear && .DiagramType == DefaultGraphType
}

func ( *d2graph.Object) ( func()) {
	 := make(map[string]int, len(.ChildrenArray))
	for ,  := range .ChildrenArray {
		[.AbsID()] = 
	}
	return func() {
		sort.SliceStable(.ChildrenArray, func(,  int) bool {
			return [.ChildrenArray[].AbsID()] < [.ChildrenArray[].AbsID()]
		})
	}
}

func ( *d2graph.Graph) ( func()) {
	 := make(map[string]int, len(.Objects))
	for ,  := range .Objects {
		[.AbsID()] = 
	}
	 := make(map[string]int, len(.Edges))
	for ,  := range .Edges {
		[.AbsID()] = 
	}
	 := SaveChildrenOrder(.Root)
	return func() {
		sort.SliceStable(.Objects, func(,  int) bool {
			return [.Objects[].AbsID()] < [.Objects[].AbsID()]
		})
		sort.SliceStable(.Edges, func(,  int) bool {
			,  := [.Edges[].AbsID()]
			,  := [.Edges[].AbsID()]
			if  &&  {
				return  < 
			}
			return 
		})
		()
	}
}

func ( context.Context,  *d2graph.Graph,  GraphInfo,  d2graph.LayoutGraph,  d2graph.RouteEdges) error {
	.Root.Box = &geo.Box{}

	// Before we can layout these nodes, we need to handle all nested diagrams first.
	 := make(map[string]*d2graph.Graph)
	var  []string
	var  []*d2graph.Edge
	var  []edgeIDs

	var  []*d2graph.Graph
	 := SaveOrder()
	defer ()

	// Iterate top-down from Root so all nested diagrams can process their own contents
	 := make([]*d2graph.Object, 0, len(.Root.ChildrenArray))
	 = append(, .Root.ChildrenArray...)
	var  map[*d2graph.Object]*subgraphExtraction
	var  *subgraphExtractionBatch
	if .DiagramType != GridDiagram {
		 := collectNestedExtractions()
		if len() > 1 {
			 = extractSubgraphs(, )
			 = .extractions
			 = [:0]
			for ,  := range  {
				 = append(, .container)
			}
		}
	}

	for len() > 0 {
		 := [0]
		 = [1:]

		 := .DiagramType == GridDiagram &&
			.IsContainer() && .Parent == .Root
		 := NestedGraphInfo()
		if ,  := [];  {
			 = .graphInfo
		}

		if  && .isDefault() {
			// if we are in a grid diagram, and our children have descendants
			// we need to run layout on them first, even if they are not special diagram types

			// First we extract the grid cell container as a nested graph with includeSelf=true
			// resulting in externalEdges=[A, C] and nestedGraph.Edges=[B]
			// ┌grid(g.Root)───────────────────┐    ┌grid(g.Root)───────────────────┐
			// │ ┌────┐      ┌curr───────────┐ │    │ ┌────┐                        │
			// │ │    │      │  ┌──┐    ┌──┐ │ │    │ │    │                        │
			// │ │    ├──A──►│  │  ├─B─►│  │ │ │ => │ │    │                        │
			// │ │    ├──────┼C─┼──┼───►│  │ │ │    │ │    │                        │
			// │ │    │      │  └──┘    └──┘ │ │    │ │    │                        │
			// │ └────┘      └───────────────┘ │    │ └────┘                        │
			// └───────────────────────────────┘    └───────────────────────────────┘
			, ,  := ExtractSubgraph(, true)

			// Then we layout curr as a nested graph and re-inject it
			 := .AbsID()
			 := (, , GraphInfo{}, , )
			if  != nil {
				return 
			}
			InjectNested(.Root, , false)
			.Edges = append(.Edges, ...)
			()

			// layout can replace Objects so we need to update the references we are holding onto (curr + externalEdges)
			 := make(map[string]*d2graph.Object)
			for ,  := range .Objects {
				[.AbsID()] = 
			}
			 := func( string) (*d2graph.Object, error) {
				,  := []
				if ! {
					return nil, fmt.Errorf("could not find object %#v after layout", )
				}
				return , nil
			}
			,  = ()
			if  != nil {
				return 
			}
			for ,  := range  {
				,  := ([].srcID)
				if  != nil {
					return 
				}
				.Src = 
				,  := ([].dstID)
				if  != nil {
					return 
				}
				.Dst = 
			}

			// position nested graph (excluding curr) relative to curr
			 := 0 - .TopLeft.X
			 := 0 - .TopLeft.Y
			for ,  := range .Objects {
				if  ==  {
					continue
				}
				.TopLeft.X += 
				.TopLeft.Y += 
			}
			for ,  := range .Edges {
				.Move(, )
			}

			// Then after re-injecting everything, we extract curr with includeSelf=false,
			// and externalEdges=[C], nestedGraph.Edges=[B], and graph.Edges=[A].
			// This will leave A in the graph to be routed by grid layout, and C will have cross-graph edge routing
			// Note: currently grid layout's cell-cell edge routing, and cross-graph edge routing behave the same,
			// but these are simple placeholder routings and they may be different in the future
			// ┌grid(g.Root)───────────────────┐    ┌grid(g.Root)───────────────────┐
			// │ ┌────┐      ┌curr───────────┐ │    │ ┌────┐      ┌curr───────────┐ │
			// │ │    │      │  ┌──┐    ┌──┐ │ │    │ │    │      │               │ │
			// │ │    ├──A──►│  │  ├─B─►│  │ │ │ => │ │    ├──A──►│               │ │
			// │ │    ├──────┼C─┼──┼───►│  │ │ │    │ │    │      │               │ │
			// │ │    │      │  └──┘    └──┘ │ │    │ │    │      │               │ │
			// │ └────┘      └───────────────┘ │    │ └────┘      └───────────────┘ │
			// └───────────────────────────────┘    └───────────────────────────────┘
			, ,  = ExtractSubgraph(, false)
			 = append(, ...)
			 = append(, ...)

			[] = 
			 = append(, )
			continue
		}

		if !.isDefault() {
			// empty grid or sequence can have 0 objects..
			,  := []
			if ! && !.IsConstantNear && len(.Children) == 0 {
				continue
			}

			// There is a nested diagram here, so extract its contents and process in the same way
			var  *d2graph.Graph
			var  []*d2graph.Edge
			var  []edgeIDs
			if ,  := [];  {
				 = .nestedGraph
				 = .externalEdges
				 = .externalEdgeIDs
			} else {
				, ,  = ExtractSubgraph(, .IsConstantNear)
			}
			 = append(, ...)
			 = append(, ...)

			log.Debug(, "layout nested", slog.Any("level", .Level()), slog.Any("child", .AbsID()), slog.Any("gi", ))
			 := 
			 := .NearKey
			if .IsConstantNear {
				// layout nested as a non-near
				 = GraphInfo{}
				.NearKey = nil
			}

			 := (, , , , )
			if  != nil {
				if ,  := [];  {
					.rollbackAfter(.index)
				}
				return 
			}
			// coreLayout can overwrite graph contents with newly created *Object pointers
			// so we need to update `curr` with nestedGraph's value
			if .IsConstantNear {
				 = .Root.ChildrenArray[0]
			}

			if .IsConstantNear {
				.NearKey = 
			} else {
				FitToGraph(, , geo.Spacing{})
				.TopLeft = geo.NewPoint(0, 0)
			}

			if .IsConstantNear {
				// near layout will inject these nestedGraphs
				 = append(, )
			} else {
				// We will restore the contents after running layout with child as the placeholder
				// We need to reference using ID because there may be a new object to use after coreLayout
				 := .AbsID()
				[] = 
				 = append(, )
			}
		} else if len(.ChildrenArray) > 0 {
			 = append(, .ChildrenArray...)
		}
	}

	// We can now run layout with accurate sizes of nested layout containers
	// Layout according to the type of diagram
	var  error
	if len(.Objects) > 0 {
		switch .DiagramType {
		case GridDiagram:
			log.Debug(, "layout grid", slog.Any("rootlevel", .RootLevel), slog.Any("shapes", .PrintString()))
			if  = d2grid.Layout(, );  != nil {
				return 
			}

		case SequenceDiagram:
			log.Debug(, "layout sequence", slog.Any("rootlevel", .RootLevel), slog.Any("shapes", .PrintString()))
			 = d2sequence.Layout(, , )
			if  != nil {
				return 
			}
		default:
			log.Debug(, "default layout", slog.Any("rootlevel", .RootLevel), slog.Any("shapes", .PrintString()))
			 := (, )
			if  != nil {
				return 
			}
		}
	}

	if len() > 0 {
		 = d2near.Layout(, , )
		if  != nil {
			return 
		}
	}

	 := make(map[string]*d2graph.Object)
	for ,  := range .Objects {
		[.AbsID()] = 
	}

	// With the layout set, inject all the extracted graphs
	for ,  := range  {
		 := []
		// we have to find the object by ID because coreLayout can replace the Objects in graph
		,  := []
		if ! {
			return fmt.Errorf("could not find object %#v after layout", )
		}
		InjectNested(, , true)
		PositionNested(, )
	}

	if len() > 0 {
		// update map with injected objects
		for ,  := range .Objects {
			[.AbsID()] = 
		}

		// Restore cross-graph edges and route them
		.Edges = append(.Edges, ...)
		for ,  := range  {
			 := []
			// update object references
			,  := [.srcID]
			if ! {
				return fmt.Errorf("could not find object %#v after layout", .srcID)
			}
			.Src = 
			,  := [.dstID]
			if ! {
				return fmt.Errorf("could not find object %#v after layout", .dstID)
			}
			.Dst = 
		}

		 = (, , )
		if  != nil {
			return 
		}
		// need to update pointers if layout engine performs edge routing
		for ,  := range  {
			 := []
			,  := [.srcID]
			if ! {
				return fmt.Errorf("could not find object %#v after routing", .srcID)
			}
			.Src = 
			,  := [.dstID]
			if ! {
				return fmt.Errorf("could not find object %#v after routing", .dstID)
			}
			.Dst = 
		}
	}

	if  := validateObjectPositions(.Objects);  != nil {
		return 
	}

	log.Debug(, "done", slog.Any("rootlevel", .RootLevel), slog.Any("shapes", .PrintString()))
	return 
}

func ( context.Context,  *d2graph.Graph,  []*d2graph.Edge) error {
	for ,  := range  {
		// TODO replace simple straight line edge routing
		.Route = []*geo.Point{.Src.Center(), .Dst.Center()}
		.TraceToShape(.Route, 0, 1)
		if .Label.Value != "" {
			.LabelPosition = go2.Pointer(label.InsideMiddleCenter.String())
		}
	}
	return nil
}

func ( *d2graph.Object) ( GraphInfo) {
	if .Graph.RootLevel == 0 && .IsConstantNear() {
		.IsConstantNear = true
	}
	if .IsSequenceDiagram() {
		.DiagramType = SequenceDiagram
	} else if .IsGridDiagram() {
		.DiagramType = GridDiagram
	}
	return 
}

type edgeIDs struct {
	srcID, dstID string
}

type subgraphExtractionSpec struct {
	container   *d2graph.Object
	includeSelf bool
	graphInfo   GraphInfo
}

type subgraphExtraction struct {
	nestedGraph     *d2graph.Graph
	externalEdges   []*d2graph.Edge
	externalEdgeIDs []edgeIDs
	graphInfo       GraphInfo
	index           int
	restoreInto     *d2graph.Object
}

type subgraphExtractionBatch struct {
	g                  *d2graph.Graph
	specs              []subgraphExtractionSpec
	extractions        map[*d2graph.Object]*subgraphExtraction
	restoreParentOrder []func()
}

// collectNestedExtractions returns the topmost nested diagrams in the same
// breadth-first order used by LayoutNested. Their object sets are disjoint, so
// they can be partitioned out of the parent graph together.
func collectNestedExtractions( *d2graph.Graph) []subgraphExtractionSpec {
	 := make([]*d2graph.Object, 0, len(.Root.ChildrenArray))
	 = append(, .Root.ChildrenArray...)
	var  []subgraphExtractionSpec
	for len() > 0 {
		 := [0]
		 = [1:]
		 := NestedGraphInfo()
		if !.isDefault() {
			if !.IsConstantNear && len(.Children) == 0 {
				continue
			}
			 = append(, subgraphExtractionSpec{
				container:   ,
				includeSelf: .IsConstantNear,
				graphInfo:   ,
			})
			continue
		}
		 = append(, .ChildrenArray...)
	}
	return 
}

// extractSubgraphs is the one-pass equivalent of calling ExtractSubgraph for
// each disjoint nested diagram in order. An edge crossing two nested diagrams
// belongs to the first extraction, matching the sequential implementation.
func extractSubgraphs( *d2graph.Graph,  []subgraphExtractionSpec) *subgraphExtractionBatch {
	 := make(map[*d2graph.Object]*subgraphExtraction, len())
	 := &subgraphExtractionBatch{
		g:           ,
		specs:       ,
		extractions: ,
	}
	 := make(map[*d2graph.Object]int, len())
	 := make(map[*d2graph.Object]struct{})
	for ,  := range  {
		[.container] = 
		 := .container
		if .includeSelf {
			 = .container.Parent
			if  != nil {
				if ,  := []; ! {
					[] = struct{}{}
					.restoreParentOrder = append(.restoreParentOrder, SaveChildrenOrder())
				}
			}
		}
		 := d2graph.NewGraph()
		.Data = cloneGraphData(.Data)
		.RootLevel = int(.container.Level())
		if .includeSelf {
			.RootLevel--
		}
		.Root.Attributes = .container.Attributes
		.Root.Box = &geo.Box{}
		.Root.LabelPosition = .container.LabelPosition
		.Root.IconPosition = .container.IconPosition
		[.container] = &subgraphExtraction{
			nestedGraph: ,
			graphInfo:   .graphInfo,
			index:       ,
			restoreInto: ,
		}
	}

	 := make(map[*d2graph.Object]int, len(.Objects))
	 := func( *d2graph.Object) (int, bool) {
		if ,  := [];  {
			return , true
		}
		for  := ;  != nil;  = .Parent {
			,  := []
			if ! {
				continue
			}
			if [].includeSelf ||  !=  {
				return , true
			}
			break
		}
		return 0, false
	}

	 := make([]*d2graph.Object, 0, len(.Objects))
	for ,  := range .Objects {
		,  := ()
		if ! {
			 = append(, )
			continue
		}
		[] = 
		 := [[].container]
		.nestedGraph.Objects = append(.nestedGraph.Objects, )
	}
	.Objects = 

	 := make([]*d2graph.Edge, 0, len(.Edges))
	for ,  := range .Edges {
		,  := (.Src)
		if d2sequence.IsLifelineEnd(.Dst) {
			if  {
				 := [[].container]
				.nestedGraph.Edges = append(.nestedGraph.Edges, )
			} else {
				 = append(, )
			}
			continue
		}

		,  := (.Dst)
		if  &&  &&  ==  {
			 := [[].container]
			.nestedGraph.Edges = append(.nestedGraph.Edges, )
			continue
		}
		if ! && ! {
			 = append(, )
			continue
		}

		 := 
		if ! ||  &&  <  {
			 = 
		}
		 := [[].container]
		.externalEdges = append(.externalEdges, )
		.externalEdgeIDs = append(.externalEdgeIDs, edgeIDs{
			srcID: .Src.AbsID(),
			dstID: .Dst.AbsID(),
		})
	}
	.Edges = 

	// Mutate parent/root references only after all memberships have been
	// classified; doing so earlier would change ancestry for later diagrams.
	for ,  := range  {
		 := [.container]
		for ,  := range .nestedGraph.Objects {
			.Graph = .nestedGraph
		}
		if .includeSelf {
			if .container.Parent != nil {
				.container.Parent.RemoveChild(.container)
			}
			.nestedGraph.Root.ChildrenArray = []*d2graph.Object{.container}
			.container.Parent = .nestedGraph.Root
			.nestedGraph.Root.Children[strings.ToLower(.container.ID)] = .container
		} else {
			.nestedGraph.Root.ChildrenArray = append(.nestedGraph.Root.ChildrenArray, .container.ChildrenArray...)
			for ,  := range .container.ChildrenArray {
				.Parent = .nestedGraph.Root
				.nestedGraph.Root.Children[strings.ToLower(.ID)] = 
			}
			for  := range .container.Children {
				delete(.container.Children, )
			}
			.container.ChildrenArray = nil
		}
	}

	return 
}

// rollbackAfter restores sibling diagrams that the batched fast path extracted
// ahead of the diagram whose recursive layout failed. The failing diagram and
// all earlier diagrams remain extracted, matching sequential ExtractSubgraph
// side effects at the same error point.
func ( *subgraphExtractionBatch) ( int) {
	for  :=  + 1;  < len(.specs); ++ {
		 := .specs[]
		 := .extractions[.container]
		InjectNested(.restoreInto, .nestedGraph, false)
		.g.Edges = append(.g.Edges, .externalEdges...)
	}
	for ,  := range .restoreParentOrder {
		()
	}
}

// Clone JSON-shaped source configuration for nested layout calls so a layout engine
// cannot change the configuration of the parent or another nested diagram.
func cloneGraphData( map[string]interface{}) map[string]interface{} {
	if  == nil {
		return nil
	}
	 := make(map[string]interface{}, len())
	for ,  := range  {
		[] = cloneGraphDataValue()
	}
	return 
}

func cloneGraphDataValue( interface{}) interface{} {
	switch value := .(type) {
	case map[string]interface{}:
		return cloneGraphData()
	case []interface{}:
		 := make([]interface{}, len())
		for ,  := range  {
			[] = ()
		}
		return 
	default:
		return 
	}
}

func ( *d2graph.Object,  bool) ( *d2graph.Graph,  []*d2graph.Edge,  []edgeIDs) {
	// includeSelf: when we have a constant near or a grid cell that is a container,
	// we want to include itself in the nested graph, not just its descendants,
	 = d2graph.NewGraph()
	.Data = cloneGraphData(.Graph.Data)
	.RootLevel = int(.Level())
	if  {
		.RootLevel--
	}
	.Root.Attributes = .Attributes
	.Root.Box = &geo.Box{}
	.Root.LabelPosition = .LabelPosition
	.Root.IconPosition = .IconPosition

	 := func( *d2graph.Object) bool {
		if  {
			return .IsDescendantOf()
		}
		return .Parent.IsDescendantOf()
	}

	// separate out nested edges
	 := .Graph
	 := make([]*d2graph.Edge, 0, len(.Edges))
	for ,  := range .Edges {
		 := (.Src)
		if d2sequence.IsLifelineEnd(.Dst) {
			// special handling for lifelines since their edge.Dst is a special Object
			if  {
				.Edges = append(.Edges, )
			} else {
				 = append(, )
			}
			continue
		}
		 := (.Dst)
		if  &&  {
			.Edges = append(.Edges, )
		} else if  ||  {
			 = append(, )
			// we need these AbsIDs when reconnecting since parent references may become stale
			 = append(, edgeIDs{
				srcID: .Src.AbsID(),
				dstID: .Dst.AbsID(),
			})
		} else {
			 = append(, )
		}
	}
	.Edges = 

	// separate out nested objects
	 := make([]*d2graph.Object, 0, len(.Objects))
	for ,  := range .Objects {
		if () {
			.Objects = append(.Objects, )
		} else {
			 = append(, )
		}
	}
	.Objects = 

	// update object and new root references
	for ,  := range .Objects {
		.Graph = 
	}

	if  {
		// remove container parent's references
		if .Parent != nil {
			.Parent.RemoveChild()
		}

		// set root references
		.Root.ChildrenArray = []*d2graph.Object{}
		.Parent = .Root
		.Root.Children[strings.ToLower(.ID)] = 
	} else {
		// set root references
		.Root.ChildrenArray = append(.Root.ChildrenArray, .ChildrenArray...)
		for ,  := range .ChildrenArray {
			.Parent = .Root
			.Root.Children[strings.ToLower(.ID)] = 
		}

		// remove container's references
		for  := range .Children {
			delete(.Children, )
		}
		.ChildrenArray = nil
	}

	return , , 
}

func ( *d2graph.Object,  *d2graph.Graph,  bool) {
	 := .Graph
	for ,  := range .Root.ChildrenArray {
		.Parent = 
		if .Children == nil {
			.Children = make(map[string]*d2graph.Object)
		}
		.Children[strings.ToLower(.ID)] = 
		.ChildrenArray = append(.ChildrenArray, )
	}
	for ,  := range .Objects {
		.Graph = 
	}
	.Objects = append(.Objects, .Objects...)
	.Edges = append(.Edges, .Edges...)

	if  {
		if .Root.LabelPosition != nil {
			.LabelPosition = .Root.LabelPosition
		}
		if .Root.IconPosition != nil {
			.IconPosition = .Root.IconPosition
		}
		.Attributes = .Root.Attributes
	}
}

func ( *d2graph.Object,  *d2graph.Graph) {
	// tl, _ := boundingBox(nestedGraph)
	// Note: assumes nestedGraph's layout has contents positioned relative to 0,0
	 := .TopLeft.X //- tl.X
	 := .TopLeft.Y //- tl.Y
	if  == 0 &&  == 0 {
		return
	}
	for ,  := range .Objects {
		.TopLeft.X += 
		.TopLeft.Y += 
	}
	for ,  := range .Edges {
		.Move(, )
	}
}

func boundingBox( *d2graph.Graph) (,  *geo.Point) {
	if len(.Objects) == 0 {
		return geo.NewPoint(0, 0), geo.NewPoint(0, 0)
	}
	 = geo.NewPoint(math.Inf(1), math.Inf(1))
	 = geo.NewPoint(math.Inf(-1), math.Inf(-1))

	for ,  := range .Objects {
		if .TopLeft == nil {
			panic(.AbsID())
		}
		.X = math.Min(.X, .TopLeft.X)
		.Y = math.Min(.Y, .TopLeft.Y)
		.X = math.Max(.X, .TopLeft.X+.Width)
		.Y = math.Max(.Y, .TopLeft.Y+.Height)
	}

	return , 
}

func validateObjectPositions( []*d2graph.Object) error {
	for ,  := range  {
		if .TopLeft == nil {
			continue
		}
		if math.IsInf(.TopLeft.X, 0) || math.IsInf(.TopLeft.Y, 0) {
			return fmt.Errorf("object %q has invalid position with infinity value: x=%f, y=%f", .AbsID(), .TopLeft.X, .TopLeft.Y)
		}
	}
	return nil
}

func ( *d2graph.Object,  *d2graph.Graph,  geo.Spacing) {
	var ,  float64
	 = .Root.Width
	 = .Root.Height
	if  == 0 ||  == 0 {
		,  := boundingBox()
		 = .X - .X
		 = .Y - .Y
	}
	.Width = .Left +  + .Right
	.Height = .Top +  + .Bottom
}