1package authoring23import (4 "crypto/sha256"5 "encoding/hex"6 "encoding/json"7 "fmt"8 "math"9 "sort"10 "strconv"11 "strings"12)1314type RequestKind string1516const (17 RequestFeatures RequestKind = "features"18 RequestRaster RequestKind = "raster"19 RequestAsset RequestKind = "asset"20)2122// Request is one exact acquisition planned without touching the network.23type Request struct {24 ID string `json:"id"`25 AcquisitionID string `json:"acquisition"`26 Kind RequestKind `json:"kind"`27 Source string `json:"source"`28 Adapter string `json:"adapter"`29 AdapterVersion string `json:"adapterVersion"`30 Locator string `json:"-"`31 IdentityLocator string `json:"locator"`32 MediaType string `json:"mediaType,omitempty"`33 License string `json:"license,omitempty"`34 Attribution string `json:"attribution,omitempty"`35 Raster string `json:"raster,omitempty"`36 Asset string `json:"asset,omitempty"`37 Zoom int64 `json:"zoom,omitempty"`38 X int64 `json:"x,omitempty"`39 Y int64 `json:"y,omitempty"`40 MaxBytes int64 `json:"maxBytes"`41}4243type PlannedRequest struct {44 Request45 Cached bool `json:"cached"`46 EstimateBytes int64 `json:"estimateBytes,omitempty"`47}4849// Plan is the complete inspectable work graph for one build.50type Plan struct {51 Project string `json:"project"`52 Title string `json:"title"`53 ProjectDigest string `json:"projectDigest"`54 World string `json:"world"`55 Requests []PlannedRequest `json:"requests"`56 Estimated int64 `json:"estimatedBytes"`57 Cached int `json:"cachedRequests"`58 Licenses []Obligation `json:"licenses,omitempty"`59 Budgets BuildBudgets `json:"budgets"`60 RasterTiles int64 `json:"rasterTiles"`61 RasterPixels int64 `json:"rasterPixels"`62 Output string `json:"output"`63}6465type Obligation struct {66 Source string `json:"source"`67 License string `json:"license,omitempty"`68 Attribution string `json:"attribution,omitempty"`69}7071func PlanProject(project Project, cache *Cache, output string) (Plan, error) {72 budgets, err := project.Budgets.resolved()73 if err != nil {74 return Plan{}, err75 }76 digest, err := projectDigest(project)77 if err != nil {78 return Plan{}, err79 }80 plan := Plan{81 Project: project.ID, Title: project.Title, ProjectDigest: digest,82 World: project.Target.World, Output: output, Budgets: budgets,83 }84 appendRequest := func(request PlannedRequest) error {85 if len(plan.Requests) >= budgets.Requests {86 return fmt.Errorf("build plans more than %d requests", budgets.Requests)87 }88 request.MaxBytes = budgets.RequestBytes89 plan.Requests = append(plan.Requests, request)90 if request.EstimateBytes > math.MaxInt64-plan.Estimated {91 return fmt.Errorf("build byte estimate overflows")92 }93 plan.Estimated += request.EstimateBytes94 if plan.Estimated > budgets.TotalBytes {95 return fmt.Errorf("build estimate %d exceeds total byte budget %d", plan.Estimated, budgets.TotalBytes)96 }97 return nil98 }99 for _, source := range project.Sources {100 request, err := featureRequest(project, source)101 if err != nil {102 return Plan{}, err103 }104 planned := PlannedRequest{Request: request, EstimateBytes: source.EstimateBytes}105 planned.Cached = cache != nil && cache.Has(requestCacheKey(request))106 if err := appendRequest(planned); err != nil {107 return Plan{}, err108 }109 plan.Licenses = append(plan.Licenses, Obligation{Source: source.ID, License: source.License, Attribution: source.Attribution})110 }111 for _, raster := range project.Rasters {112 requests, tiles, pixels, err := rasterRequests(project, raster, budgets)113 if err != nil {114 return Plan{}, err115 }116 if tiles > budgets.RasterTiles-plan.RasterTiles || pixels > budgets.RasterPixels-plan.RasterPixels {117 return Plan{}, fmt.Errorf("raster %s exceeds the remaining raster budget", raster.ID)118 }119 plan.RasterTiles += tiles120 plan.RasterPixels += pixels121 each := int64(0)122 if len(requests) > 0 {123 each = raster.EstimateBytes / int64(len(requests))124 }125 for index, request := range requests {126 estimate := each127 if index == len(requests)-1 {128 estimate += raster.EstimateBytes - each*int64(len(requests))129 }130 planned := PlannedRequest{Request: request, EstimateBytes: estimate}131 planned.Cached = cache != nil && cache.Has(requestCacheKey(request))132 if err := appendRequest(planned); err != nil {133 return Plan{}, err134 }135 }136 plan.Licenses = append(plan.Licenses, Obligation{Source: raster.ID, License: raster.License, Attribution: raster.Attribution})137 }138 for _, asset := range project.Assets {139 request := assetRequest(project, asset)140 planned := PlannedRequest{Request: request, EstimateBytes: asset.EstimateBytes}141 planned.Cached = cache != nil && cache.Has(requestCacheKey(request))142 if err := appendRequest(planned); err != nil {143 return Plan{}, err144 }145 plan.Licenses = append(plan.Licenses, Obligation{Source: asset.ID, License: asset.License, Attribution: asset.Attribution})146 }147 sort.Slice(plan.Requests, func(i, j int) bool { return plan.Requests[i].ID < plan.Requests[j].ID })148 markCachedCaptureSets(&plan, cache)149 sort.Slice(plan.Licenses, func(i, j int) bool { return plan.Licenses[i].Source < plan.Licenses[j].Source })150 return plan, nil151}152153func markCachedCaptureSets(plan *Plan, cache *Cache) {154 plan.Cached = 0155 requestIndexes := make(map[string]int, len(plan.Requests))156 for index := range plan.Requests {157 plan.Requests[index].Cached = false158 requestIndexes[plan.Requests[index].ID] = index159 }160 if cache == nil {161 return162 }163 for _, group := range planCaptureGroups(*plan) {164 requests := make([]Request, len(group.Requests))165 for index := range group.Requests {166 requests[index] = group.Requests[index].Request167 }168 set, err := cache.LatestSet(captureSetID(requests))169 if err != nil || validateSetForRequests(set, requests) != nil {170 continue171 }172 for _, grouped := range group.Requests {173 index := requestIndexes[grouped.ID]174 plan.Requests[index].Cached = true175 plan.Cached++176 }177 }178}179180func assetRequest(project Project, asset Asset) Request {181 request := Request{182 Kind: RequestAsset, Source: asset.ID, Adapter: "asset-file",183 Locator: project.ResolveLocator(asset.Locator), IdentityLocator: asset.Locator,184 MediaType: asset.MediaType, License: asset.License, Attribution: asset.Attribution,185 Asset: asset.ID,186 }187 finalizeRequest(&request)188 return request189}190191func featureRequest(project Project, source Source) (Request, error) {192 adapter, err := defaultAdapterRegistry().Lookup(source.Adapter)193 if err != nil {194 return Request{}, fmt.Errorf("source %s uses %w", source.ID, err)195 }196 return adapter.PlanFeature(project, source)197}198199func rasterRequests(project Project, raster Raster, budgets BuildBudgets) ([]Request, int64, int64, error) {200 makeRequest := func(locator, identity string, zoom, x, y int64) Request {201 request := Request{202 Kind: RequestRaster, Source: raster.ID, Adapter: raster.Adapter,203 Locator: locator, IdentityLocator: identity, MediaType: raster.MediaType,204 License: raster.License, Attribution: raster.Attribution,205 Raster: raster.ID, Zoom: zoom, X: x, Y: y,206 }207 finalizeRequest(&request)208 return request209 }210 if raster.Adapter == "raster-file" {211 tiles, err := pyramidTileCount(raster.MaxZoom)212 if err != nil || tiles > budgets.RasterTiles {213 return nil, 0, 0, fmt.Errorf("raster %s exceeds tile budget %d", raster.ID, budgets.RasterTiles)214 }215 pixels, err := checkedPixels(tiles, raster.TileSize)216 if err != nil || pixels > budgets.RasterPixels {217 return nil, 0, 0, fmt.Errorf("raster %s exceeds pixel budget %d", raster.ID, budgets.RasterPixels)218 }219 return []Request{makeRequest(project.ResolveLocator(raster.Locator), raster.Locator, 0, 0, 0)}, tiles, pixels, nil220 }221 var tileCount int64222 for _, level := range raster.Levels {223 width, height := level.MaxX-level.MinX+1, level.MaxY-level.MinY+1224 if width > math.MaxInt64/height || tileCount > budgets.RasterTiles-width*height {225 return nil, 0, 0, fmt.Errorf("raster %s exceeds tile budget %d", raster.ID, budgets.RasterTiles)226 }227 tileCount += width * height228 }229 pixels, err := checkedPixels(tileCount, raster.TileSize)230 if err != nil || pixels > budgets.RasterPixels {231 return nil, 0, 0, fmt.Errorf("raster %s exceeds pixel budget %d", raster.ID, budgets.RasterPixels)232 }233 var requests []Request234 for _, level := range raster.Levels {235 for y := level.MinY; y <= level.MaxY; y++ {236 for x := level.MinX; x <= level.MaxX; x++ {237 identity := strings.NewReplacer(238 "{z}", strconv.FormatInt(level.Zoom, 10), "{x}", strconv.FormatInt(x, 10), "{y}", strconv.FormatInt(y, 10),239 "{TileMatrix}", strconv.FormatInt(level.Zoom, 10), "{TileCol}", strconv.FormatInt(x, 10), "{TileRow}", strconv.FormatInt(y, 10),240 ).Replace(raster.Locator)241 requests = append(requests, makeRequest(project.ResolveLocator(identity), identity, level.Zoom, x, y))242 }243 }244 }245 return requests, tileCount, pixels, nil246}247248func pyramidTileCount(maxZoom int64) (int64, error) {249 var total int64250 for zoom := int64(0); zoom <= maxZoom; zoom++ {251 if zoom >= 32 {252 return 0, fmt.Errorf("zoom %d overflows tile count", zoom)253 }254 level := int64(1) << (2 * zoom)255 if total > math.MaxInt64-level {256 return 0, fmt.Errorf("zoom %d overflows tile count", zoom)257 }258 total += level259 }260 return total, nil261}262263func checkedPixels(tiles, tileSize int64) (int64, error) {264 if tileSize <= 0 || tileSize > math.MaxInt64/tileSize {265 return 0, fmt.Errorf("tile size overflows pixel count")266 }267 perTile := tileSize * tileSize268 if tiles > math.MaxInt64/perTile {269 return 0, fmt.Errorf("raster pixel count overflows")270 }271 return tiles * perTile, nil272}273274func requestID(request Request) string {275 canonical := struct {276 Source, Raster, Asset, Acquisition string277 }{request.Source, request.Raster, request.Asset, request.AcquisitionID}278 if canonical.Acquisition == "" {279 canonical.Acquisition = acquisitionID(request)280 }281 data, _ := json.Marshal(canonical)282 digest := sha256.Sum256(data)283 return hex.EncodeToString(digest[:])284}285286func acquisitionID(request Request) string {287 canonical := struct {288 Kind, Adapter, Version, Locator, MediaType string289 Zoom, X, Y int64290 }{string(request.Kind), request.Adapter, request.AdapterVersion, request.IdentityLocator, request.MediaType, request.Zoom, request.X, request.Y}291 data, _ := json.Marshal(canonical)292 digest := sha256.Sum256(data)293 return hex.EncodeToString(digest[:])294}295296func finalizeRequest(request *Request) {297 request.AdapterVersion = adapterVersion(request.Adapter)298 request.AcquisitionID = acquisitionID(*request)299 request.ID = requestID(*request)300}301302func adapterVersion(adapter string) string {303 registered, err := defaultAdapterRegistry().Lookup(adapter)304 if err != nil {305 return adapter + "/unknown"306 }307 return registered.Version()308}309310func requestCacheKey(request Request) string {311 if request.AcquisitionID != "" {312 return request.AcquisitionID313 }314 return request.ID315}316317func projectDigest(project Project) (string, error) {318 data, err := json.Marshal(project)319 if err != nil {320 return "", fmt.Errorf("canonicalize project: %w", err)321 }322 digest := sha256.Sum256(data)323 return hex.EncodeToString(digest[:]), nil324}325326func extentString(extent [4]float64) string {327 values := make([]string, len(extent))328 for index, value := range extent {329 values[index] = strconv.FormatFloat(value, 'g', -1, 64)330 }331 return strings.Join(values, ",")332}