ipplot/ipplot.go

/*
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

package ipplot

import (
	"errors"
	"image"
	"image/color"
	"log"
	"math"
	"net"
	"sort"

	"gioui.org/f32"
	"gioui.org/io/key"
	"gioui.org/io/pointer"
	"gioui.org/layout"
	"gioui.org/op"
	"gioui.org/op/clip"
	"gioui.org/op/paint"
	"gioui.org/unit"
	"gioui.org/widget/material"
)

var cursorBlock = &Block{blockType: Transient, ipW: 1, ipH: 1}

/*
There is no point in drawing blocks that we cannot see.  For
prefixes longer than 24 bits, as well as prefixes longer
than 24 bits plus the current zoom level, we will skip the
layout phase, possibly favoring aggregate effects, like
bloom, as an indication of block population and density.
*/
var drawHorizon int = 24

/*
Any more than 12 bits past the current zoom level, and
blocks become increasingly difficult to identify, let alone
click or tap. Better we cut off interaction at a sensible
level, providing visual indicators of when blocks can or
cannot be "touched."
*/
var touchHorizon int = 12

var ipv4IANAReservedStrings = []string{
	"0.0.0.0/8",
	"10.0.0.0/8",
	"172.16.0.0/12",
	"192.168.0.0/16",
	"100.64.0.0/10",
	"127.0.0.0/8",
	"169.254.0.0/16",
	"192.0.0.0/24",
	"192.0.2.0/24",
	"192.31.196.0/24",
	"192.52.193.0/24",
	"192.88.99.0/24",
	"192.175.48.0/24",
	"198.18.0.0/15",
	"198.51.0.0/24",
	"203.0.113.0/24",
	"224.0.0.0/4",
	"240.0.0.0/4",
}

type IPPlotState int

const (
	StateNeutral           IPPlotState = iota // Nothing happening
	StateZoom                                 // Zoom view in/out
	StatePrimeBlock                           // Ready to act on pressed block
	StateSelectBlock                          // Update info for selected block
	StateMoveBlock                            // Permit block movement
	StateSelectOverlapping                    // Select block above or below current
	StateResizeBlock                          // Resize block in place
)

type BlockType int

const (
	Allocation   BlockType = iota // User allocation
	IANAPrivate                   // RFC1918
	IANAReserved                  // All other IANA reserved
	Transient                     // For intermediate calculations
)

type BlockOverlap int

const (
	OverlapAny     BlockOverlap = iota
	OverlapShorter              // Cannot contain other blocks
	OverlapLonger               // Cannot be contained by other blocks
	OverlapNone                 // Cannot overlap other blocks, at all
)

type BlockStatus int

const (
	Nascent        BlockStatus = iota // Not persistent
	Reserved                          // Persistent but not assigned
	Assigned                          // Persistent and assigned
	Decommissioned                    // Pending reassignment
)

type IPBlock interface {
	ContainsPoint(uint64, uint64) bool
	IPCoordinates() (uint64, uint64)
	IPDimensions() (uint64, uint64)
	LessThanOrEq(IPBlock) bool
	PixelCoordinates(pxMax image.Point) (unit.Dp, unit.Dp)
	PixelDimensions(pxMax image.Point) (unit.Dp, unit.Dp)
	ToPrefix() IPPrefix
}

type Block struct {
	blockType BlockType
	overlap   BlockOverlap
	immutable bool
	status    BlockStatus
	ipX       uint64
	ipY       uint64
	ipW       uint64
	ipH       uint64
}

func (b1 *Block) Eq(b2 *Block) bool {
	return b1.ipX == b2.ipX &&
		b1.ipY == b2.ipY &&
		b1.ipW == b2.ipW &&
		b1.ipH == b2.ipH
}

func (b1 *Block) LessThanOrEq(b2 IPBlock) bool {
	return b1.ToPrefix().LessThanOrEq(b2.ToPrefix())
}

func (b *Block) ContainsPoint(ipX, ipY uint64) bool {
	// <= (x+w-1) must be used because x+w can wrap to 0!
	return (b.ipX <= ipX) &&
		(ipX <= (b.ipX + b.ipW - 1)) &&
		(b.ipY <= ipY) &&
		(ipY <= (b.ipY + b.ipH - 1))
}

func (b *Block) IPCoordinates() (uint64, uint64) {
	return b.ipX, b.ipY
}

func (b *Block) IPDimensions() (uint64, uint64) {
	return b.ipW, b.ipH
}

func (b *Block) PixelCoordinates(
	pxMax image.Point,
) (unit.Dp, unit.Dp) {
	// TODO: assume IPv4, for now; support IPv6 later.
	ipMax := uint64(0xffff)
	minMax := minPixelMax(pxMax)
	return IPToPxCoords(b.ipX, b.ipY, ipMax, minMax)
}

func (b *Block) PixelDimensions(
	pxMax image.Point,
) (unit.Dp, unit.Dp) {
	// TODO: assume IPv4, for now; support IPv6 later.
	ipMax := uint64(0xffff)
	minMax := minPixelMax(pxMax)
	return IPToPxCoords(b.ipW, b.ipH, ipMax, minMax)
}

func (b *Block) ToPrefix() IPPrefix {
	var p IPPrefix = IPv4FromGeometry(
		b.ipX,
		b.ipY,
		b.ipW,
		b.ipH,
	)
	return p
}

func NewIPBlock(p IPPrefix, t BlockType) IPBlock {
	b := &Block{blockType: t}

	switch t {
	case Allocation:
	case IANAPrivate:
		b.overlap = OverlapLonger
		b.immutable = true
		b.status = Reserved
	case IANAReserved:
		b.overlap = OverlapNone
		b.immutable = true
		b.status = Reserved
	}
	b.ipX, b.ipY, b.ipW, b.ipH = p.ToGeometry()

	return b
}

func IPToPxCoords(
	x,
	y,
	ipMax uint64,
	pxMax int,
) (unit.Dp, unit.Dp) {
	dx := float64(pxMax) / float64(ipMax)
	dy := dx

	return unit.Dp(float64(x) * dx), unit.Dp(float64(y) * dy)
}

func PxToIPCoords(
	x,
	y float32,
	ipMax uint64,
	pxMax int,
) (uint64, uint64) {
	dx := float64(ipMax) / float64(pxMax)
	dy := dx

	return uint64(float64(x) * dx), uint64(float64(y) * dy)
}

func minPixelMax(pxMax image.Point) int {
	return int(math.Min(float64(pxMax.X), float64(pxMax.Y)))
}

type IPPlot struct {
	state        IPPlotState
	selected     int // index of selected block
	hovered      int // index of hovered block
	zoomLevel    int // display only prefixes of length >= 2z
	ptrX         float32
	ptrY         float32
	freshHovered bool // hover triggered; change to int flag?
	blocktip     material.LabelStyle
	blocks       []IPBlock
}

func (ipp *IPPlot) handleInputEvents(
	gtx layout.Context,
	maxPt int,
) {
	// If we hover over a block and nothing was hovered
	// before, then we say the hover event is "fresh." If we
	// are, instead, simply recalculating which block is being
	// hovered over, then we set "freshHovered" back to false.
	// This is a fairly opaque nomenclature, so
	// TODO: find a better name for "freshHovered"
	for _, e := range gtx.Events(ipp) {
		if e, ok := e.(pointer.Event); ok {
			switch {
			case ipp.state == StateNeutral && e.Type == pointer.Press:
				ipp.hovered =
					calculateHovered(
						ipp.blocks,
						ipp.ptrX,
						ipp.ptrY,
						maxPt,
					)
				ipp.freshHovered = true
				if ipp.hovered >= 0 {
					ipp.state = StatePrimeBlock
				}
			case e.Type == pointer.Move:
				ipp.freshHovered = false
				ipp.ptrX = e.Position.X
				ipp.ptrY = e.Position.Y
			}
		}
	}
	if !ipp.freshHovered {
		ipp.hovered =
			calculateHovered(
				ipp.blocks,
				ipp.ptrX,
				ipp.ptrY,
				maxPt,
			)
	}
}

func (ipp *IPPlot) subscribeToInputEvents(
	gtx layout.Context,
	maxPt int,
) {
	area := clip.Rect(image.Rect(
		0,
		0,
		maxPt,
		maxPt,
	)).Push(gtx.Ops)

	mask := pointer.Move
	mask |= pointer.Press
	mask |= pointer.Release
	pointer.InputOp{Tag: ipp, Types: mask}.Add(gtx.Ops)
	area.Pop()

	key.InputOp{Tag: ipp, Keys: "z|x"}.Add(gtx.Ops)
}

func (ipp *IPPlot) drawBlocks(gtx layout.Context) {
	for i, ipb := range ipp.blocks {
		x, y := ipb.PixelCoordinates(gtx.Constraints.Max)
		w, h := ipb.PixelDimensions(gtx.Constraints.Max)

		// <= (x+w-1) must be used because x+w can wrap to 0!
		minPt := f32.Pt(float32(x), float32(y))
		maxPt := f32.Pt(float32(x+w)-1, float32(y+h)-1)

		if i == ipp.hovered {
			drawHoveredBlock(gtx, minPt, maxPt)
		} else {
			drawIANAReservedBlock(gtx, minPt, maxPt)
		}
	}
}

func (ipp *IPPlot) drawBlocktip(
	gtx layout.Context,
	maxPt int,
) {
	var block IPBlock

	if ipp.hovered >= 0 {
		block = ipp.blocks[ipp.hovered]
	} else {
		block = cursorBlock
		// TODO: assume IPv4, for now; support IPv6 later.
		ipMax := uint64(0xffff)

		cursorBlock.ipX, cursorBlock.ipY =
			PxToIPCoords(ipp.ptrX, ipp.ptrY, ipMax, maxPt)
	}

	ipp.blocktip.Text = block.ToPrefix().String()

	defer op.Offset(image.Point{
		X: gtx.Dp(unit.Dp(ipp.ptrX) + 15),
		Y: gtx.Dp(unit.Dp(ipp.ptrY)),
	}).Push(gtx.Ops).Pop()

	ipp.blocktip.Layout(gtx)
}

func (ipp *IPPlot) Layout(gtx layout.Context) {
	maxPt := minPixelMax(gtx.Constraints.Max)

	ipp.handleInputEvents(gtx, maxPt)
	ipp.subscribeToInputEvents(gtx, maxPt)
	ipp.drawBlocks(gtx)
	ipp.drawBlocktip(gtx, maxPt)
}

func drawHoveredBlock(
	gtx layout.Context,
	minPt,
	maxPt f32.Point,
) {
	// TODO: extremely silly; fix this nonsense
	rect := clip.Rect(image.Rect(
		gtx.Dp(unit.Dp(minPt.X)),
		gtx.Dp(unit.Dp(minPt.Y)),
		gtx.Dp(unit.Dp(maxPt.X)),
		gtx.Dp(unit.Dp(maxPt.Y)),
	))
	color := color.NRGBA{R: 0xa0, G: 0x70, B: 0x10, A: 0x50}
	border :=
		clip.Stroke{Path: rect.Path(), Width: 0.2}

	paint.FillShape(gtx.Ops, color, rect.Op())
	paint.FillShape(gtx.Ops, color, border.Op())
}

type f32Rect struct {
	Min, Max f32.Point
}

func (r f32Rect) Path(ops *op.Ops) clip.PathSpec {
	var p clip.Path

	p.Begin(ops)
	p.MoveTo(r.Min)
	p.Line(f32.Pt(r.Max.X, r.Min.Y))
	p.Line(r.Max)
	p.Line(f32.Pt(r.Min.X, r.Max.Y))
	p.Line(r.Min)

	return p.End()
}

func (r f32Rect) Op(ops *op.Ops) clip.Op {
	return clip.Outline{Path: r.Path(ops)}.Op()
}

func (r f32Rect) Push(ops *op.Ops) clip.Stack {
	return r.Op(ops).Push(ops)
}

func drawIANAReservedBlock(
	gtx layout.Context,
	minPt,
	maxPt f32.Point,
) {
	// TODO: extremely silly; fix this nonsense
	rect := clip.Rect(image.Rect(
		gtx.Dp(unit.Dp(minPt.X)),
		gtx.Dp(unit.Dp(minPt.Y)),
		gtx.Dp(unit.Dp(maxPt.X)),
		gtx.Dp(unit.Dp(maxPt.Y)),
	))
	black := color.NRGBA{A: 0xff}
	blue := color.NRGBA{R: 0x10, G: 0x30, B: 0x50, A: 0x50}
	border :=
		clip.Stroke{Path: rect.Path(), Width: 0.2}

	paint.FillShape(gtx.Ops, blue, rect.Op())
	paint.FillShape(gtx.Ops, black, border.Op())

	return
}

func calculateHovered(
	bs []IPBlock,
	x, y float32,
	maxPt int,
) int {
	// TODO: assume IPv4, for now; support IPv6 later.
	ipMax := uint64(0xffff)
	ipX, ipY := PxToIPCoords(x, y, ipMax, maxPt)
	hovered, _ := findSmallestOverlappingIPBlock(bs, ipX, ipY)

	return hovered
}

/*
Binary search for smallest block that contains point.

Return index to smallest block or error.
*/
func findSmallestOverlappingIPBlock(
	ipbs []IPBlock,
	ipX,
	ipY uint64,
) (int, error) {
	a := 0
	b := len(ipbs)
	if b == 0 {
		return -1, errors.New("empty slice")
	}
	if b == 1 && ipbs[0].ContainsPoint(ipX, ipY) {
		return 0, nil
	}
	if b == 1 {
		return -1, errors.New("no overlapping block")
	}

	cursorBlock.ipX = ipX
	cursorBlock.ipY = ipY

	// Bugs here can cause infinite loops. We avoid this by
	// bounding the search to its theoretical maximum
	// duration. TODO: why is +2 needed, here?
	limit := int(math.Log2(float64(len(ipbs)))) + 2
	for {
		mid := int(a + ((b - a) / 2))
		midLeft := ipbs[mid-1]
		midRight := ipbs[mid]

		if limit == 0 {
			log.Printf("midLeft: %v\n", midLeft.ToPrefix())
			log.Printf("midRight: %v\n", midRight.ToPrefix())
			log.Printf("pfx: %s, ipX: %d, ipY: %d, a: %d, b: %d, mid: %d\n", cursorBlock.ToPrefix(), ipX, ipY, a, b, mid)
			panic("loop limit reached")
		}
		limit--

		switch {
		case midLeft.ContainsPoint(ipX, ipY):
			for mid < len(ipbs) {
				if !ipbs[mid].ContainsPoint(ipX, ipY) {
					break
				}
				mid++
			}
			return mid - 1, nil
		case midRight.ContainsPoint(ipX, ipY):
			mid++
			for mid < len(ipbs) {
				if !ipbs[mid].ContainsPoint(ipX, ipY) {
					break
				}
				mid++
			}
			return mid - 1, nil
		case cursorBlock.LessThanOrEq(midLeft):
			b = mid - 1
		case midRight.LessThanOrEq(cursorBlock):
			a = mid + 1
		case cursorBlock.LessThanOrEq(midRight):
			return -1, errors.New("no overlapping block")
		default:
			log.Printf("midLeft: %v\n", midLeft.ToPrefix())
			log.Printf("midRight: %v\n", midRight.ToPrefix())
			log.Printf("pfx: %s, ipX: %d, ipY: %d, a: %d, b: %d, mid: %d\n", cursorBlock.ToPrefix(), ipX, ipY, a, b, mid)

			panic("unexpected case while finding smallest overlapping block")
		}
	}
}

func cmpIPBlocks(s []IPBlock) func(i, j int) bool {
	return func(i, j int) bool {
		si, sj := s[i], s[j]
		siPfx := si.ToPrefix()
		sjPfx := sj.ToPrefix()

		return siPfx.LessThanOrEq(sjPfx)
	}
}

func NewIPPlot(th *material.Theme) *IPPlot {
	ipp := IPPlot{
		blocktip: material.Label(th, unit.Sp(14), ""),
	}

	for _, s := range ipv4IANAReservedStrings {
		_, ipNet, _ := net.ParseCIDR(s)
		length, _ := ipNet.Mask.Size()
		pfx, _ := NewIPv4(ipNet.IP, length)
		ipb := NewIPBlock(pfx, IANAReserved)

		ipp.blocks = append(ipp.blocks, ipb)
	}
	sort.SliceStable(ipp.blocks, cmpIPBlocks(ipp.blocks))
	return &ipp
}