history.go

/*
Copyright © 2022 Johnson Shi <Johnson.Shi@microsoft.com>
*/
package history

import (
	"fmt"
	"strconv"
	"strings"

	"github.com/asottile/dockerfile"
)

// GetImageManifestLayerDockerfileCommandsHistory returns the exact Dockerfile commands
// that contributed to the creation of each image manifest layer.
// Layers returned are sorted from bottom layers (base image layers) to top layers.
// attributionAnnotations is only added to the layer history
// if the layer is not a primary base image layer
// (i.e. only added for layers not 'FROM <primary-base-image>')
func (h *ImageHistory) GetImageManifestLayerDockerfileCommandsHistory(attributionAnnotations map[string]string) ([]ImageManifestLayerDockerfileCommandsHistory, error) {
	reversed, err := h.getReversedImageManifestLayerDockerfileCommandsHistory(attributionAnnotations)
	if err != nil {
		return nil, err
	}
	// Reverse the reversed slice to get the original order.
	var ret []ImageManifestLayerDockerfileCommandsHistory
	for i := len(reversed) - 1; i >= 0; i-- {
		ret = append(ret, reversed[i])
	}
	return ret, nil
}

// getReversedImageManifestLayerDockerfileCommandsHistory returns the exact Dockerfile commands
// that contributed to the creation of each image manifest layer (layers returned are
// reversed, i.e. sorted from top layers to bottom layers/base image layers).
// attributionAnnotations is only added to the layer history
// if the layer is not a primary base image layer
// (i.e. only added for layers not 'FROM <primary-base-image>')
func (h *ImageHistory) getReversedImageManifestLayerDockerfileCommandsHistory(attributionAnnotations map[string]string) ([]ImageManifestLayerDockerfileCommandsHistory, error) {
	imageLayerHistoryIndex := 0
	imageManifestLayerIndex := len(h.ImageManifest.Layers) - 1
	dockerfileCommandIndex := len(h.DockerfileCommands) - 1

	manifestLayerHistory := []ImageManifestLayerDockerfileCommandsHistory{}

	for imageLayerHistoryIndex < len(h.ImageLayerHistory) && imageManifestLayerIndex >= 0 && dockerfileCommandIndex >= 0 {
		layerCmd := h.DockerfileCommands[dockerfileCommandIndex]
		layerCmdInstruction := strings.ToUpper(layerCmd.Cmd)

		// CASE 1: Handle the `FROM <image>` case.
		//
		// When traversing from the bottom of the Dockerfile upwards (as we are doing now),
		// the first `FROM <image>` command encountered is the primary base image FROM import.
		//
		// We do not need to iterate over the remaining Dockerfile commands above the first `FROM <image>` command encountered,
		// because the remaining Dockerfile commands correspond to multistage build stages.
		// Those multistage build stage Dockerfile commands only produce a layer in the resulting image
		// through `COPY --from=<multistage-build-stage>` commands, which we would have already handled below.
		if layerCmdInstruction == "FROM" {
			if len(layerCmd.Value) == 0 {
				return nil, fmt.Errorf(
					"invalid Dockerfile `FROM <image>` cmd (cmd: '%s') due to missing base image reference",
					layerCmd.Original,
				)
			}
			baseImageRef := layerCmd.Value[0]

			for ; imageManifestLayerIndex >= 0; imageManifestLayerIndex-- {
				layerHistory := ImageManifestLayerDockerfileCommandsHistory{
					LayerDescriptor: h.ImageManifest.Layers[imageManifestLayerIndex],
					LayerCreationParameters: LayerCreationParameters{
						DockerfileLayerCreationType: FROMPrimaryBaseImageLayer,
						DockerfileCommands:          h.DockerfileCommands[dockerfileCommandIndex : dockerfileCommandIndex+1],
						BaseImageRef:                baseImageRef,
					},
					AttributedEntity: attributionAnnotations,
				}
				manifestLayerHistory = append(manifestLayerHistory, layerHistory)
			}

			return manifestLayerHistory, nil
		}

		// CASE 2: Handle empty layers in image layer history,
		// such as empty layers generated by `ENV` or `EXPOSE` commands.
		//
		// Empty layers DO correspond to 1 Dockerfile command instruction only.
		// Empty layers DO NOT correspond to any OCI image manifest layer.
		//
		// As such, we need to skip over this empty layer by
		// (1) incrementing the image layer history index,
		// (2) decrementing the dockerfile command index,
		// (3) leaving the image manifest layer index UNCHANGED.
		//
		// Note: Empty layers are created by instructions that don't create a layer,
		// Instructions that are *not* {FROM, ADD, COPY, RUN} will create empty layers.
		if h.ImageLayerHistory[imageLayerHistoryIndex].Size == 0 {
			imageLayerHistoryIndex++
			dockerfileCommandIndex--
			continue
		}

		// Non-Empty Layer Cases
		//
		// Handle non-empty layers in image layer history,
		// except for non-empty layers created by `FROM <image>` command (which we would have handled above).
		//
		// Non-empty layers DO correspond to EITHER
		// 		1 Dockerfile command instruction
		// 		OR multiple Dockerfile command instructions.
		// Non-empty layers DO correspond to 1 OCI image manifest layer.
		//
		// Note: Non-empty layers are created by instructions that create a layer,
		// such as `FROM`, `COPY`, `ADD`, or `RUN`.
		// Note: We should NOT enocunter any `FROM` instructions here as we would have handled it above.

		// CASE 3: Handle `COPY --from=<multistage-build-stage>` instruction.
		//
		// A `COPY --from=<multistage-build-stage>` instruction creates a layer
		// by copying contents from a previous multistage build stage.
		layerCmdFlags := layerCmd.Flags
		if copyFromFlag := getSubstringContainsCaseInsensitive(layerCmdFlags, "--from="); layerCmdInstruction == "COPY" && copyFromFlag != "" {
			// Get the stage name where the layer contents were copied from.
			// E.g. get the <builder> stage name in "--from=<builder>".
			stageName := parseStageNameFromCopyFromFlag(copyFromFlag)
			if stageName == "" {
				return nil, fmt.Errorf("could not find stage name in `%s`", copyFromFlag)
			}

			// Get the start and end indexes of the Dockerfile commands that correspond to the multistage build stage.
			multistageBuildStageStart, multistageBuildStageEnd, err := FindMultistageBuildStage(h.DockerfileCommands, stageName)
			if err != nil {
				return nil, err
			}

			// Capture *ALL* the Dockerfile commands that contributed to this `COPY --from=<multistage-build-stage>` instruction.
			//
			// First, capture the Dockerfile commands that correspond to the *ENTIRE* multistage build stage.
			//		E.g. Capture ALL of the following instructions:
			//			FROM ubuntu:22.04 as builder
			//			RUN echo "hello" > /hello.txt
			//			RUN echo "world" > /world.txt
			//			ADD file.txt /file.txt
			//		Note: The *ENTIRE* multistage build stage MUST be captured to produce an accurate detailed layer history.
			//
			// Then, capture the Dockerfile command for the `COPY --from=<multistage-build-stage>` instruction.
			//		E.g. Capture the following instruction:
			//			COPY --from=builder /hello.txt /hello.txt

			layerDockerfileCommands := make([]dockerfile.Command, multistageBuildStageEnd-multistageBuildStageStart+1)

			// We create a new slice and copy elements over to prevent overwriting the original slice.
			nCopied := copy(layerDockerfileCommands, h.DockerfileCommands[multistageBuildStageStart:multistageBuildStageEnd+1])
			if nCopied != multistageBuildStageEnd-multistageBuildStageStart+1 {
				return nil, fmt.Errorf("could not copy all Dockerfile commands for multistage build stage")
			}

			// Don't forget to append the `COPY --from=<multistage-build-stage>` instruction itself.
			layerDockerfileCommands = append(layerDockerfileCommands, layerCmd)

			// Obtain the base image ref of the `COPY --from=<multistage-build-stage>`` instruction
			// by looking at the first Dockerfile command (which should be the FROM command) in the multistage build stage.
			if len(layerDockerfileCommands) == 0 || len(layerDockerfileCommands[0].Value) == 0 {
				return nil, fmt.Errorf(
					"invalid Dockerfile `COPY --from=<multistage-build-stage>` cmd (cmd: '%s') due to missing base image reference in the `FROM` statement of the <multistage-build-stage>",
					layerCmd.Original,
				)
			}
			baseImageRef := layerDockerfileCommands[0].Value[0]

			layerHistory := ImageManifestLayerDockerfileCommandsHistory{
				LayerDescriptor: h.ImageManifest.Layers[imageManifestLayerIndex],
				LayerCreationParameters: LayerCreationParameters{
					DockerfileLayerCreationType: COPYFromMultistageBuildStageLayer,
					DockerfileCommands:          layerDockerfileCommands,
					BaseImageRef:                baseImageRef,
				},
				AttributedEntity: attributionAnnotations,
			}

			manifestLayerHistory = append(manifestLayerHistory, layerHistory)

			imageLayerHistoryIndex++
			dockerfileCommandIndex--
			imageManifestLayerIndex--
			continue
		}

		// CASE 4: Remaining cases are non-empty layers created by:
		//		COPY (except for COPY --from=<multistage-build-stage>),
		//		ADD
		//		RUN

		var layerCreationType LayerCreationType
		switch layerCmdInstruction {
		case "COPY":
			layerCreationType = COPYCommandLayer
		case "ADD":
			layerCreationType = ADDCommandLayer
		case "RUN":
			layerCreationType = RUNCommandLayer
		default:
			layerCreationType = UNKNOWNDockerfileCommandLayer
		}

		layerHistory := ImageManifestLayerDockerfileCommandsHistory{
			LayerDescriptor: h.ImageManifest.Layers[imageManifestLayerIndex],
			LayerCreationParameters: LayerCreationParameters{
				DockerfileLayerCreationType: layerCreationType,
				DockerfileCommands:          h.DockerfileCommands[dockerfileCommandIndex : dockerfileCommandIndex+1],
			},
			AttributedEntity: attributionAnnotations,
		}

		manifestLayerHistory = append(manifestLayerHistory, layerHistory)

		imageLayerHistoryIndex++
		dockerfileCommandIndex--
		imageManifestLayerIndex--
	}

	return manifestLayerHistory, nil
}

// FindMultistageBuildStage finds the start and end indexes of the
// Dockerfile commands that correspond to the multistage build stage.
// The stage is the `<multistage-build-stage>` value within
// the `COPY --from=<multistage-build-stage>` flag.
// The stage can be a stage name string or a stage number.
//
// Note: The specified build stage name can be a stage number as well, such as `--from=0`.
// See example at https://docs.docker.com/develop/develop-images/multistage-build/#:~:text=How%20does%20it,the%20final%20image.
func FindMultistageBuildStage(dockerfileCommands []dockerfile.Command, stage string) (int, int, error) {
	// Attempt to parse the stage as a stage number.
	stageNumber, err := strconv.Atoi(stage)
	if err != nil {
		// If the stage is not a stage number, then it must be a stage name string.
		return findMultistageBuildStageFromStageNameString(dockerfileCommands, stage)
	}

	return findMultistageBuildStageFromStageNumber(dockerfileCommands, stageNumber)
}

// findMultistageBuildStageFromStageNameString finds the start and end indexes
// of the Dockerfile commands that correspond to the multistage build stage.
// The stage is the `<multistage-build-stage>` value within
// the `COPY --from=<multistage-build-stage>` flag.
// The stage is a stage name string (e.g. `builder` in `COPY --from=builder`).
func findMultistageBuildStageFromStageNameString(dockerfileCommands []dockerfile.Command, stageName string) (int, int, error) {
	for i, dockerfileCommand := range dockerfileCommands {
		if isMatchingNamedMultistageBuildStageFromCommand(dockerfileCommand, stageName) {
			buildStageStartIndex := i

			buildStageEndIndex, err := findEndOfCurrentBuildStage(dockerfileCommands, buildStageStartIndex)
			if err != nil {
				return 0, 0, err
			}

			return buildStageStartIndex, buildStageEndIndex, nil
		}
	}

	return 0, 0, fmt.Errorf("could not find multistage build stage name: %s", stageName)
}

// isMatchingNamedMultistageBuildStageFromCommand checks if:
// 		1. The Dockerfile command is a `FROM` command.
// 		2. The `FROM` command is a *named* multistage build stage.
// 		3. The named multistage build stage matches the specified stage name.
//
// E.g. (`FROM ubuntu AS fooBuilder`, "fooBuilder")
//		returns TRUE as it is a MATCHING NAMED multistage build stage.
//
// E.g. (`FROM ubuntu AS fooBuilder`, "barBuilder")
//		returns FALSE as it is NOT A MATCHING NAMED multistage build stage.
//
// E.g. (`FROM ubuntu`, "builder")
//		returns FALSE as it is NOT A NAMED (UNNAMED) multistage build stage.
func isMatchingNamedMultistageBuildStageFromCommand(dockerfileCommand dockerfile.Command, stageName string) bool {
	cmd := dockerfileCommand.Cmd               // e.g. "FROM"
	cmdValueContent := dockerfileCommand.Value // e.g. []string{"ubuntu", "AS", "builderStageName"}
	cmdValueContentLen := len(cmdValueContent)

	return strings.ToUpper(cmd) == "FROM" &&
		cmdValueContentLen >= 3 &&
		strings.EqualFold(cmdValueContent[cmdValueContentLen-1], stageName) &&
		strings.ToUpper(cmdValueContent[cmdValueContentLen-2]) == "AS"
}

// findMultistageBuildStageFromStageNumber finds the start and end indexes
// of the Dockerfile commands that correspond to the multistage build stage.
// The stage is the `<multistage-build-stage>` value within
// the `COPY --from=<multistage-build-stage>` flag.
// The stage is a stage number (e.g. `0` in `COPY --from=0`).
// Note: Stage numbers start at 0.
func findMultistageBuildStageFromStageNumber(dockerfileCommands []dockerfile.Command, stageNumber int) (int, int, error) {
	buildStagesSeen := 0

	for i, dockerfileCommand := range dockerfileCommands {
		if strings.ToUpper(dockerfileCommand.Cmd) == "FROM" {
			// We will have found the multistage build stage when we:
			// 		(1) see a `FROM` instruction and
			//		(2) have previously seen the correct number of build stages.
			// Note: Stage numbers start at 0.
			if buildStagesSeen == stageNumber {
				buildStageStartIndex := i

				buildStageEndIndex, err := findEndOfCurrentBuildStage(dockerfileCommands, buildStageStartIndex)
				if err != nil {
					return 0, 0, err
				}

				return buildStageStartIndex, buildStageEndIndex, nil
			}

			buildStagesSeen++
		}
	}

	return 0, 0, fmt.Errorf("could not find multistage build stage number: %d", stageNumber)
}

// findEndOfCurrentBuildStage finds the end of the current build stage.
// The end of the current build stage is the line right before the
// next `FROM` instruction encountered.
func findEndOfCurrentBuildStage(dockerfileCommands []dockerfile.Command, buildStageStartIndex int) (int, error) {
	nextFromCommandIndex, err := findNextFromCommandIndex(dockerfileCommands, buildStageStartIndex+1)
	if err != nil {
		return buildStageStartIndex, err
	}
	buildStageEndIndex := nextFromCommandIndex - 1
	return buildStageEndIndex, nil
}

// findNextFromCommandIndex finds the index of the next encountered `FROM` command,
// starting from the specified start index.
func findNextFromCommandIndex(dockerfileCommands []dockerfile.Command, startIndex int) (int, error) {
	for i := startIndex; i < len(dockerfileCommands); i++ {
		if strings.ToUpper(dockerfileCommands[i].Cmd) == "FROM" {
			return i, nil
		}
	}

	return 0, fmt.Errorf("could not find next FROM command")
}

// Returns the stage name in a from flag (returns "builder" in "--from=builder"),
// otherwise returns an empty string.
func parseStageNameFromCopyFromFlag(copyFromFlag string) string {
	_, after, found := strings.Cut(copyFromFlag, "--from=")
	if !found {
		return ""
	}

	return after
}

// getSubstringContainsCaseInsensitive returns the first string in
// the given string slice that contains the given substring, otherwise an empty string.
func getSubstringContainsCaseInsensitive(haystack []string, substr string) string {
	for _, s := range haystack {
		if strings.Contains(strings.ToLower(s), strings.ToLower(substr)) {
			return s
		}
	}
	return ""
}

// GetSimplifiedImageManifestLayerDockerfileCommandsHistory returns the exact Dockerfile commands
// that contributed to the creation of each image manifest layer (simplified format).
// attributionAnnotations is only added to the layer history
// if the layer is not a primary base image layer
// (i.e. only added for layers not 'FROM <primary-base-image>')
func GetSimplifiedImageManifestLayerDockerfileCommandsHistory(manifestLayerHistory []ImageManifestLayerDockerfileCommandsHistory) []SimplifiedImageManifestLayerDockerfileCommandsHistory {
	var simplified []SimplifiedImageManifestLayerDockerfileCommandsHistory
	for _, h := range manifestLayerHistory {
		var concatenatedCmds []string
		for _, c := range h.LayerCreationParameters.DockerfileCommands {
			concatenatedCmds = append(concatenatedCmds, c.Original)
		}
		simplified = append(simplified, SimplifiedImageManifestLayerDockerfileCommandsHistory{
			LayerDigest:                 h.LayerDescriptor.Digest,
			DockerfileLayerCreationType: h.LayerCreationParameters.DockerfileLayerCreationType,
			DockerfileCommands:          concatenatedCmds,
			BaseImageRef:                h.LayerCreationParameters.BaseImageRef,
			AttributedEntity:            h.AttributedEntity,
		})
	}
	return simplified
}