func TestMergeRenderableNode(t *testing.T) {
	node1 := render.RenderableNode{
		ID:         "foo",
		LabelMajor: "",
		LabelMinor: "minor",
		Rank:       "",
		Pseudo:     false,
		Node:       report.MakeNode().WithAdjacent("a1"),
		Origins:    report.MakeIDList("o1"),
	}
	node2 := render.RenderableNode{
		ID:         "foo",
		LabelMajor: "major",
		LabelMinor: "",
		Rank:       "rank",
		Pseudo:     false,
		Node:       report.MakeNode().WithAdjacent("a2"),
		Origins:    report.MakeIDList("o2"),
	}
	want := render.RenderableNode{
		ID:           "foo",
		LabelMajor:   "major",
		LabelMinor:   "minor",
		Rank:         "rank",
		Pseudo:       false,
		Node:         report.MakeNode().WithAdjacency(report.MakeIDList("a1", "a2")),
		Origins:      report.MakeIDList("o1", "o2"),
		EdgeMetadata: report.EdgeMetadata{},
	}
	have := node1.Merge(node2)
	if !reflect.DeepEqual(want, have) {
		t.Error(test.Diff(want, have))
	}
}

// Set the list of endpoints for the given hostname.
func (c *multiClient) Set(hostname string, endpoints []string) {
	wg := sync.WaitGroup{}
	wg.Add(len(endpoints))
	clients := make(chan clientTuple, len(endpoints))
	for _, endpoint := range endpoints {
		go func(endpoint string) {
			c.sema.acquire()
			defer c.sema.release()
			defer wg.Done()

			client, err := c.clientFactory(hostname, endpoint)
			if err != nil {
				log.Errorf("Error creating new app client: %v", err)
				return
			}

			details, err := client.Details()
			if err != nil {
				log.Errorf("Error fetching app details: %v", err)
				return
			}

			clients <- clientTuple{details, client}
		}(endpoint)
	}

	wg.Wait()
	close(clients)
	c.mtx.Lock()
	defer c.mtx.Unlock()

	// Start any new apps, and replace the list of app ids for this hostname
	hostIDs := report.MakeIDList()
	for tuple := range clients {
		hostIDs = hostIDs.Add(tuple.ID)

		_, ok := c.clients[tuple.ID]
		if !ok {
			c.clients[tuple.ID] = tuple.AppClient
			tuple.AppClient.ControlConnection()
		}
	}
	c.ids[hostname] = hostIDs

	// Remove apps that are no longer referenced (by id) from any hostname
	allReferencedIDs := report.MakeIDList()
	for _, ids := range c.ids {
		allReferencedIDs = allReferencedIDs.Add(ids...)
	}
	for id, client := range c.clients {
		if !allReferencedIDs.Contains(id) {
			client.Stop()
			delete(c.clients, id)
		}
	}
}

func assertAdjacent(t *testing.T, n report.RenderableNode, ids ...string) {
	want := report.MakeIDList(ids...)

	if have := n.Adjacency; !reflect.DeepEqual(want, have) {
		t.Fatalf("want adjacency list %v, have %v", want, have)
	}
}

// MakeRenderableNodes converts a topology to a set of RenderableNodes
func MakeRenderableNodes(t report.Topology) RenderableNodes {
	result := RenderableNodes{}
	for id, nmd := range t.Nodes {
		rn := NewRenderableNode(id).WithNode(nmd)
		rn.Origins = report.MakeIDList(id)
		if hostNodeID, ok := nmd.Metadata[report.HostNodeID]; ok {
			rn.Origins = rn.Origins.Add(hostNodeID)
		}
		result[id] = rn
	}

	// Push EdgeMetadata to both ends of the edges
	for srcID, srcNode := range result {
		for dstID, emd := range srcNode.Edges {
			srcNode.EdgeMetadata = srcNode.EdgeMetadata.Flatten(emd)

			dstNode := result[dstID]
			dstNode.EdgeMetadata = dstNode.EdgeMetadata.Flatten(emd.Reversed())
			result[dstID] = dstNode
		}

		result[srcID] = srcNode
	}
	return result
}

func TestFilterRender(t *testing.T) {
	renderer := render.FilterUnconnected(
		mockRenderer{RenderableNodes: render.RenderableNodes{
			"foo": {ID: "foo", Adjacency: report.MakeIDList("bar"), NodeMetadata: report.MakeNodeMetadata()},
			"bar": {ID: "bar", Adjacency: report.MakeIDList("foo"), NodeMetadata: report.MakeNodeMetadata()},
			"baz": {ID: "baz", Adjacency: report.MakeIDList(), NodeMetadata: report.MakeNodeMetadata()},
		}})
	want := render.RenderableNodes{
		"foo": {ID: "foo", Adjacency: report.MakeIDList("bar"), NodeMetadata: report.MakeNodeMetadata()},
		"bar": {ID: "bar", Adjacency: report.MakeIDList("foo"), NodeMetadata: report.MakeNodeMetadata()},
	}
	have := sterilize(renderer.Render(report.MakeReport()), true)
	if !reflect.DeepEqual(want, have) {
		t.Errorf("want %+v, have %+v", want, have)
	}
}

func ids(nodes RenderableNodes) report.IDList {
	result := report.MakeIDList()
	for id := range nodes {
		result = result.Add(id)
	}
	return result
}

func TestMapEdge(t *testing.T) {
	selector := func(_ report.Report) report.Topology {
		return report.Topology{
			NodeMetadatas: report.NodeMetadatas{
				"foo": report.NewNodeMetadata(map[string]string{"id": "foo"}),
				"bar": report.NewNodeMetadata(map[string]string{"id": "bar"}),
			},
			Adjacency: report.Adjacency{
				">foo": report.MakeIDList("bar"),
				">bar": report.MakeIDList("foo"),
			},
			EdgeMetadatas: report.EdgeMetadatas{
				"foo|bar": report.EdgeMetadata{WithBytes: true, BytesIngress: 1, BytesEgress: 2},
				"bar|foo": report.EdgeMetadata{WithBytes: true, BytesIngress: 3, BytesEgress: 4},
			},
		}
	}

	identity := func(nmd report.NodeMetadata) (render.RenderableNode, bool) {
		return render.NewRenderableNode(nmd.Metadata["id"], "", "", "", nmd), true
	}

	mapper := render.Map{
		MapFunc: func(nodes render.RenderableNode) (render.RenderableNode, bool) {
			return render.RenderableNode{ID: "_" + nodes.ID}, true
		},
		Renderer: render.LeafMap{
			Selector: selector,
			Mapper:   identity,
			Pseudo:   nil,
		},
	}

	want := render.AggregateMetadata{
		render.KeyBytesIngress: 1,
		render.KeyBytesEgress:  2,
	}
	have := mapper.AggregateMetadata(report.MakeReport(), "_foo", "_bar")
	if !reflect.DeepEqual(want, have) {
		t.Errorf("want %+v, have %+v", want, have)
	}
}

func TestMapRender3(t *testing.T) {
	// 3. Check we can remap adjacencies
	mapper := render.Map{
		MapFunc: func(nodes render.RenderableNode) (render.RenderableNode, bool) {
			return render.RenderableNode{ID: "_" + nodes.ID}, true
		},
		Renderer: mockRenderer{RenderableNodes: render.RenderableNodes{
			"foo": {ID: "foo", Adjacency: report.MakeIDList("baz")},
			"baz": {ID: "baz", Adjacency: report.MakeIDList("foo")},
		}},
	}
	want := render.RenderableNodes{
		"_foo": {ID: "_foo", Adjacency: report.MakeIDList("_baz")},
		"_baz": {ID: "_baz", Adjacency: report.MakeIDList("_foo")},
	}
	have := mapper.Render(report.MakeReport())
	if !reflect.DeepEqual(want, have) {
		t.Errorf("want %+v, have %+v", want, have)
	}
}

func TestMapEdge(t *testing.T) {
	selector := func(_ report.Report) report.Topology {
		return report.Topology{
			NodeMetadatas: report.NodeMetadatas{
				"foo": report.MakeNodeMetadataWith(map[string]string{"id": "foo"}),
				"bar": report.MakeNodeMetadataWith(map[string]string{"id": "bar"}),
			},
			Adjacency: report.Adjacency{
				">foo": report.MakeIDList("bar"),
				">bar": report.MakeIDList("foo"),
			},
			EdgeMetadatas: report.EdgeMetadatas{
				"foo|bar": report.EdgeMetadata{EgressPacketCount: newu64(1), EgressByteCount: newu64(2)},
				"bar|foo": report.EdgeMetadata{EgressPacketCount: newu64(3), EgressByteCount: newu64(4)},
			},
		}
	}

	identity := func(nmd report.NodeMetadata) render.RenderableNodes {
		return render.RenderableNodes{nmd.Metadata["id"]: render.NewRenderableNode(nmd.Metadata["id"], "", "", "", nmd)}
	}

	mapper := render.Map{
		MapFunc: func(nodes render.RenderableNode) render.RenderableNodes {
			id := "_" + nodes.ID
			return render.RenderableNodes{id: render.RenderableNode{ID: id}}
		},
		Renderer: render.LeafMap{
			Selector: selector,
			Mapper:   identity,
			Pseudo:   nil,
		},
	}

	if want, have := (report.EdgeMetadata{
		EgressPacketCount: newu64(1),
		EgressByteCount:   newu64(2),
	}), mapper.EdgeMetadata(report.MakeReport(), "_foo", "_bar"); !reflect.DeepEqual(want, have) {
		t.Error(test.Diff(want, have))
	}
}

// NewRenderableNode makes a new RenderableNode
func NewRenderableNode(id string) RenderableNode {
	return RenderableNode{
		ID:           id,
		LabelMajor:   "",
		LabelMinor:   "",
		Rank:         "",
		Pseudo:       false,
		Origins:      report.MakeIDList(),
		EdgeMetadata: report.EdgeMetadata{},
		Node:         report.MakeNode(),
	}
}

func TestMergeRenderableNode(t *testing.T) {
	node1 := render.RenderableNode{
		ID:         "foo",
		LabelMajor: "",
		LabelMinor: "minor",
		Rank:       "",
		Pseudo:     false,
		Adjacency:  report.MakeIDList("a1"),
		Origins:    report.MakeIDList("o1"),
	}
	node2 := render.RenderableNode{
		ID:         "foo",
		LabelMajor: "major",
		LabelMinor: "",
		Rank:       "rank",
		Pseudo:     false,
		Adjacency:  report.MakeIDList("a2"),
		Origins:    report.MakeIDList("o2"),
	}

	want := render.RenderableNode{
		ID:         "foo",
		LabelMajor: "major",
		LabelMinor: "minor",
		Rank:       "rank",
		Pseudo:     false,
		Adjacency:  report.MakeIDList("a1", "a2"),
		Origins:    report.MakeIDList("o1", "o2"),
	}
	node1.Merge(node2)

	if !reflect.DeepEqual(want, node1) {
		t.Errorf("want %+v, have %+v", want, node1)
	}
}

func TestIDList(t *testing.T) {
	have := report.MakeIDList("alpha", "mu", "zeta")
	have = have.Add("alpha")
	have = have.Add("nu")
	have = have.Add("mu")
	have = have.Add("alpha")
	have = have.Add("alpha")
	have = have.Add("epsilon")
	have = have.Add("delta")
	if want := report.IDList([]string{"alpha", "delta", "epsilon", "mu", "nu", "zeta"}); !reflect.DeepEqual(want, have) {
		t.Errorf("want %+v, have %+v", want, have)
	}
}

func (w Weave) tagContainer(r report.Report, containerIDPrefix, macAddress string, ips []string) {
	for nodeid, nmd := range r.Container.NodeMetadatas {
		idPrefix := nmd.Metadata[docker.ContainerID][:12]
		if idPrefix != containerIDPrefix {
			continue
		}

		existingIPs := report.MakeIDList(docker.ExtractContainerIPs(nmd)...)
		existingIPs = existingIPs.Add(ips...)
		nmd.Metadata[docker.ContainerIPs] = strings.Join(existingIPs, " ")
		nmd.Metadata[WeaveMACAddress] = macAddress
		r.Container.NodeMetadatas[nodeid] = nmd
		break
	}
}

// EdgeMetadata gives the metadata of an edge from the perspective of the
// srcRenderableID. Since an edgeID can have multiple edges on the address
// level, it uses the supplied mapping function to translate address IDs to
// renderable node (mapped) IDs.
func (m LeafMap) EdgeMetadata(rpt report.Report, srcRenderableID, dstRenderableID string) report.EdgeMetadata {
	t := m.Selector(rpt)
	metadata := report.EdgeMetadata{}
	for edgeID, edgeMeta := range t.EdgeMetadatas {
		src, dst, ok := report.ParseEdgeID(edgeID)
		if !ok {
			log.Printf("bad edge ID %q", edgeID)
			continue
		}
		srcs, dsts := report.MakeIDList(src), report.MakeIDList(dst)
		if src != report.TheInternet {
			mapped := m.Mapper(t.NodeMetadatas[src])
			srcs = ids(mapped)
		}
		if dst != report.TheInternet {
			mapped := m.Mapper(t.NodeMetadatas[dst])
			dsts = ids(mapped)
		}
		if srcs.Contains(srcRenderableID) && dsts.Contains(dstRenderableID) {
			metadata = metadata.Flatten(edgeMeta)
		}
	}
	return metadata
}

// Tag implements Tagger.
func (w *Weave) Tag(r report.Report) (report.Report, error) {
	w.mtx.RLock()
	defer w.mtx.RUnlock()

	// Put information from weaveDNS on the container nodes
	for _, entry := range w.status.DNS.Entries {
		if entry.Tombstone > 0 {
			continue
		}
		nodeID := report.MakeContainerNodeID(w.hostID, entry.ContainerID)
		node, ok := r.Container.Nodes[nodeID]
		if !ok {
			continue
		}
		hostnames := report.IDList(strings.Fields(node.Metadata[WeaveDNSHostname]))
		hostnames = hostnames.Add(strings.TrimSuffix(entry.Hostname, "."))
		node.Metadata[WeaveDNSHostname] = strings.Join(hostnames, " ")
	}

	// Put information from weave ps on the container nodes
	psEntries, err := w.ps()
	if err != nil {
		return r, nil
	}
	containersByPrefix := map[string]report.Node{}
	for _, node := range r.Container.Nodes {
		prefix := node.Metadata[docker.ContainerID][:12]
		containersByPrefix[prefix] = node
	}
	for _, e := range psEntries {
		node, ok := containersByPrefix[e.containerIDPrefix]
		if !ok {
			continue
		}

		existingIPs := report.MakeIDList(docker.ExtractContainerIPs(node)...)
		existingIPs = existingIPs.Add(e.ips...)
		node.Metadata[docker.ContainerIPs] = strings.Join(existingIPs, " ")
		node.Metadata[WeaveMACAddress] = e.macAddress
	}
	return r, nil
}

func (m Map) render(rpt report.Report) (RenderableNodes, map[string]string) {
	input := m.Renderer.Render(rpt)
	output := RenderableNodes{}
	mapped := map[string]string{}             // input node ID -> output node ID
	adjacencies := map[string]report.IDList{} // output node ID -> input node Adjacencies

	for _, inRenderable := range input {
		outRenderable, ok := m.MapFunc(inRenderable)
		if !ok {
			continue
		}

		existing, ok := output[outRenderable.ID]
		if ok {
			outRenderable.Merge(existing)
		}

		output[outRenderable.ID] = outRenderable
		mapped[inRenderable.ID] = outRenderable.ID
		adjacencies[outRenderable.ID] = adjacencies[outRenderable.ID].Add(inRenderable.Adjacency...)
	}

	// Rewrite Adjacency for new node IDs.
	// NB we don't do pseudo nodes here; we assume the input graph
	// is properly-connected, and if the map func dropped a node,
	// we drop links to it.
	for outNodeID, inAdjacency := range adjacencies {
		outAdjacency := report.MakeIDList()
		for _, inAdjacent := range inAdjacency {
			if outAdjacent, ok := mapped[inAdjacent]; ok {
				outAdjacency = outAdjacency.Add(outAdjacent)
			}
		}
		outNode := output[outNodeID]
		outNode.Adjacency = outAdjacency
		output[outNodeID] = outNode
	}

	return output, mapped
}

func (f Filter) render(rpt report.Report) (RenderableNodes, int) {
	output := RenderableNodes{}
	inDegrees := map[string]int{}
	filtered := 0
	for id, node := range f.Renderer.Render(rpt) {
		if f.FilterFunc(node) {
			output[id] = node
			inDegrees[id] = 0
		} else {
			filtered++
		}
	}

	// Deleted nodes also need to be cut as destinations in adjacency lists.
	for id, node := range output {
		newAdjacency := report.MakeIDList()
		for _, dstID := range node.Adjacency {
			if _, ok := output[dstID]; ok {
				newAdjacency = newAdjacency.Add(dstID)
				inDegrees[dstID]++
			}
		}
		node.Adjacency = newAdjacency
		output[id] = node
	}

	// Remove unconnected pseudo nodes, see #483.
	for id, inDegree := range inDegrees {
		if inDegree > 0 {
			continue
		}
		node := output[id]
		if !node.Pseudo || len(node.Adjacency) > 0 {
			continue
		}
		delete(output, id)
		filtered++
	}
	return output, filtered
}

func (m Map) render(rpt report.Report) (RenderableNodes, map[string]report.IDList) {
	var (
		input         = m.Renderer.Render(rpt)
		output        = RenderableNodes{}
		mapped        = map[string]report.IDList{} // input node ID -> output node IDs
		adjacencies   = map[string]report.IDList{} // output node ID -> input node Adjacencies
		localNetworks = LocalNetworks(rpt)
	)

	// Rewrite all the nodes according to the map function
	for _, inRenderable := range input {
		for _, outRenderable := range m.MapFunc(inRenderable, localNetworks) {
			existing, ok := output[outRenderable.ID]
			if ok {
				outRenderable = outRenderable.Merge(existing)
			}

			output[outRenderable.ID] = outRenderable
			mapped[inRenderable.ID] = mapped[inRenderable.ID].Add(outRenderable.ID)
			adjacencies[outRenderable.ID] = adjacencies[outRenderable.ID].Merge(inRenderable.Adjacency)
		}
	}

	// Rewrite Adjacency for new node IDs.
	for outNodeID, inAdjacency := range adjacencies {
		outAdjacency := report.MakeIDList()
		for _, inAdjacent := range inAdjacency {
			for _, outAdjacent := range mapped[inAdjacent] {
				outAdjacency = outAdjacency.Add(outAdjacent)
			}
		}
		outNode := output[outNodeID]
		outNode.Adjacency = outAdjacency
		output[outNodeID] = outNode
	}

	return output, mapped
}

			Nodes: report.Nodes{
				ClientAddressNodeID: report.MakeNode().WithMetadata(map[string]string{
					endpoint.Addr:     ClientIP,
					report.HostNodeID: ClientHostNodeID,
				}).WithEdge(ServerAddressNodeID, report.EdgeMetadata{
					MaxConnCountTCP: newu64(3),
				}),

				ServerAddressNodeID: report.MakeNode().WithMetadata(map[string]string{
					endpoint.Addr:     ServerIP,
					report.HostNodeID: ServerHostNodeID,
				}),

				UnknownAddress1NodeID: report.MakeNode().WithMetadata(map[string]string{
					endpoint.Addr: UnknownClient1IP,
				}).WithAdjacency(report.MakeIDList(ServerAddressNodeID)),

				UnknownAddress2NodeID: report.MakeNode().WithMetadata(map[string]string{
					endpoint.Addr: UnknownClient2IP,
				}).WithAdjacency(report.MakeIDList(ServerAddressNodeID)),

				UnknownAddress3NodeID: report.MakeNode().WithMetadata(map[string]string{
					endpoint.Addr: UnknownClient3IP,
				}).WithAdjacency(report.MakeIDList(ServerAddressNodeID)),

				RandomAddressNodeID: report.MakeNode().WithMetadata(map[string]string{
					endpoint.Addr: RandomClientIP,
				}).WithAdjacency(report.MakeIDList(ServerAddressNodeID)),
			},
		},
		Host: report.Topology{

	uncontainedServerID  = render.MakePseudoNodeID(render.UncontainedID, test.ServerHostName)
	unknownPseudoNode1ID = render.MakePseudoNodeID("10.10.10.10", test.ServerIP, "80")
	unknownPseudoNode2ID = render.MakePseudoNodeID("10.10.10.11", test.ServerIP, "80")
	unknownPseudoNode1   = func(adjacency report.IDList) render.RenderableNode {
		return render.RenderableNode{
			ID:           unknownPseudoNode1ID,
			LabelMajor:   "10.10.10.10",
			Pseudo:       true,
			NodeMetadata: report.MakeNodeMetadata(),
			EdgeMetadata: report.EdgeMetadata{
				EgressPacketCount: newu64(70),
				EgressByteCount:   newu64(700),
			},
			Adjacency: adjacency,
			Origins: report.MakeIDList(
				test.UnknownClient1NodeID,
				test.UnknownClient2NodeID,
			),
		}
	}
	unknownPseudoNode2 = func(adjacency report.IDList) render.RenderableNode {
		return render.RenderableNode{
			ID:           unknownPseudoNode2ID,
			LabelMajor:   "10.10.10.11",
			Pseudo:       true,
			NodeMetadata: report.MakeNodeMetadata(),
			EdgeMetadata: report.EdgeMetadata{
				EgressPacketCount: newu64(50),
				EgressByteCount:   newu64(500),
			},
			Adjacency: adjacency,
			Origins: report.MakeIDList(