orchard

  1package main
  2
  3import (
  4	"context"
  5	"fmt"
  6	"net/http"
  7	"regexp"
  8	"sort"
  9	"strings"
 10	"sync"
 11	"time"
 12)
 13
 14// A model writing code from search results invents package names, and it is the
 15// one mistake in a code answer that a reader cannot see. A syntax error shows
 16// up the moment they run it. `pip install flask-yfinance-cache` fails at a point
 17// where they have already decided the answer was good.
 18//
 19// So every package the answer imports is looked up in the registry that would
 20// have to have it, the same way an entity link is fetched and checked to be the
 21// thing it claims. Four registries, all keyless.
 22
 23// Dependency is one package named by the code, and whether it exists.
 24type Dependency struct {
 25	Name string
 26	Eco  string
 27	URL  string
 28	// Found is only meaningful when Checked is true. A registry that did not
 29	// answer proves nothing, and saying so is better than guessing either way.
 30	Found   bool
 31	Checked bool
 32}
 33
 34const (
 35	maxDepChecks = 14
 36	depTimeout   = 6 * time.Second
 37)
 38
 39// verifyDeps looks up every package the blocks import. It is safe to call with
 40// no network: an unreachable registry leaves Checked false.
 41func verifyDeps(ctx context.Context, client *http.Client, blocks []CodeBlock) []Dependency {
 42	found := map[string]Dependency{}
 43	for _, b := range blocks {
 44		for _, d := range depsIn(b) {
 45			key := d.Eco + " " + d.Name
 46			if _, seen := found[key]; !seen {
 47				found[key] = d
 48			}
 49		}
 50	}
 51	if len(found) == 0 {
 52		return nil
 53	}
 54
 55	list := make([]Dependency, 0, len(found))
 56	for _, d := range found {
 57		list = append(list, d)
 58	}
 59	sort.Slice(list, func(a, b int) bool {
 60		if list[a].Eco != list[b].Eco {
 61			return list[a].Eco < list[b].Eco
 62		}
 63		return list[a].Name < list[b].Name
 64	})
 65	if len(list) > maxDepChecks {
 66		list = list[:maxDepChecks]
 67	}
 68
 69	ctx, cancel := context.WithTimeout(ctx, depTimeout*2)
 70	defer cancel()
 71
 72	var wg sync.WaitGroup
 73	sema := make(chan struct{}, 4)
 74	for i := range list {
 75		wg.Add(1)
 76		go func(d *Dependency) {
 77			defer wg.Done()
 78			sema <- struct{}{}
 79			defer func() { <-sema }()
 80			d.Found, d.Checked = registryHas(ctx, client, *d)
 81		}(&list[i])
 82	}
 83	wg.Wait()
 84	return list
 85}
 86
 87// depsIn reads the packages out of one block. Shell blocks are read too, since
 88// an install line names the package exactly and an import only names the module
 89// it happens to expose.
 90func depsIn(b CodeBlock) []Dependency {
 91	switch normalLang(b.Lang, b.File) {
 92	case "python":
 93		return pythonDeps(b.Code)
 94	case "javascript":
 95		return jsDeps(b.Code)
 96	case "go":
 97		return goDeps(b.Code)
 98	case "dockerfile":
 99		return dockerDeps(b.Code)
100	}
101	switch b.Lang {
102	case "sh", "bash", "shell", "console", "zsh", "":
103		return shellDeps(b.Code)
104	}
105	return nil
106}
107
108var (
109	pyImport   = regexp.MustCompile(`(?m)^\s*(?:from\s+([A-Za-z_][\w.]*)|import\s+([A-Za-z_][\w.]*(?:\s*,\s*[A-Za-z_][\w.]*)*))`)
110	jsImport   = regexp.MustCompile(`(?:from\s+|require\(\s*|import\(\s*)["']([^"'\n]+)["']`)
111	goImport   = regexp.MustCompile(`(?m)^\s*(?:_\s+|\w+\s+)?"([a-z0-9.\-]+\.[a-z]{2,}/[^"\n]+)"`)
112	dockerFrom = regexp.MustCompile(`(?im)^\s*FROM\s+(?:--platform=\S+\s+)?(\S+)`)
113	pipInstall = regexp.MustCompile(`(?i)\bpip3?\s+install\s+([^\n|&;]+)`)
114	npmInstall = regexp.MustCompile(`(?i)\bnpm\s+(?:install|i|add)\s+([^\n|&;]+)|\b(?:bun|yarn|pnpm)\s+add\s+([^\n|&;]+)`)
115	dockerRun  = regexp.MustCompile(`(?im)\bdocker\s+(?:run|pull|create)\s+(.+)$`)
116)
117
118func pythonDeps(code string) []Dependency {
119	var out []Dependency
120	for _, m := range pyImport.FindAllStringSubmatch(code, -1) {
121		names := []string{m[1]}
122		if m[2] != "" {
123			names = strings.Split(m[2], ",")
124		}
125		for _, n := range names {
126			mod := strings.TrimSpace(n)
127			if i := strings.Index(mod, "."); i > 0 {
128				mod = mod[:i]
129			}
130			if mod == "" || pyStdlib[mod] {
131				continue
132			}
133			out = append(out, Dependency{Name: pyDistribution(mod), Eco: "pypi"})
134		}
135	}
136	return out
137}
138
139// pyDistribution maps a module name to the package that installs it, for the
140// handful where they differ. Everything else is imported by its own name.
141func pyDistribution(mod string) string {
142	switch mod {
143	case "bs4":
144		return "beautifulsoup4"
145	case "yaml":
146		return "pyyaml"
147	case "cv2":
148		return "opencv-python"
149	case "PIL":
150		return "pillow"
151	case "dateutil":
152		return "python-dateutil"
153	case "sklearn":
154		return "scikit-learn"
155	case "dotenv":
156		return "python-dotenv"
157	case "serial":
158		return "pyserial"
159	case "OpenSSL":
160		return "pyopenssl"
161	case "jwt":
162		return "pyjwt"
163	case "psycopg2":
164		return "psycopg2-binary"
165	case "flask_cors":
166		return "flask-cors"
167	case "flask_caching":
168		return "flask-caching"
169	}
170	return strings.ReplaceAll(mod, "_", "-")
171}
172
173func jsDeps(code string) []Dependency {
174	var out []Dependency
175	for _, m := range jsImport.FindAllStringSubmatch(code, -1) {
176		spec := m[1]
177		if strings.HasPrefix(spec, ".") || strings.HasPrefix(spec, "/") || strings.HasPrefix(spec, "http") {
178			continue
179		}
180		spec = strings.TrimPrefix(spec, "node:")
181		parts := strings.Split(spec, "/")
182		name := parts[0]
183		if strings.HasPrefix(spec, "@") && len(parts) > 1 {
184			name = parts[0] + "/" + parts[1]
185		}
186		if nodeBuiltin[name] {
187			continue
188		}
189		out = append(out, Dependency{Name: name, Eco: "npm"})
190	}
191	return out
192}
193
194func goDeps(code string) []Dependency {
195	var out []Dependency
196	for _, m := range goImport.FindAllStringSubmatch(code, -1) {
197		if mod := goModuleRoot(m[1]); mod != "" {
198			out = append(out, Dependency{Name: mod, Eco: "go"})
199		}
200	}
201	return out
202}
203
204// goModuleRoot trims an import path back to the module the proxy knows about,
205// which for the three big forges is the first three elements.
206func goModuleRoot(path string) string {
207	parts := strings.Split(path, "/")
208	switch parts[0] {
209	case "github.com", "gitlab.com", "bitbucket.org", "codeberg.org":
210		if len(parts) < 3 {
211			return ""
212		}
213		return strings.Join(parts[:3], "/")
214	}
215	return path
216}
217
218func dockerDeps(code string) []Dependency {
219	var out []Dependency
220	for _, m := range dockerFrom.FindAllStringSubmatch(code, -1) {
221		if img := dockerRepo(m[1]); img != "" {
222			out = append(out, Dependency{Name: img, Eco: "docker"})
223		}
224	}
225	return out
226}
227
228func shellDeps(code string) []Dependency {
229	var out []Dependency
230	for _, m := range pipInstall.FindAllStringSubmatch(code, -1) {
231		for _, name := range installArgs(m[1]) {
232			out = append(out, Dependency{Name: name, Eco: "pypi"})
233		}
234	}
235	for _, m := range npmInstall.FindAllStringSubmatch(code, -1) {
236		for _, name := range installArgs(m[1] + m[2]) {
237			if !nodeBuiltin[name] {
238				out = append(out, Dependency{Name: name, Eco: "npm"})
239			}
240		}
241	}
242	for _, m := range dockerRun.FindAllStringSubmatch(code, -1) {
243		if img := dockerRepo(imageArg(m[1])); img != "" {
244			out = append(out, Dependency{Name: img, Eco: "docker"})
245		}
246	}
247	return out
248}
249
250// installArgs takes the package names off an install line, dropping flags and
251// version pins.
252func installArgs(s string) []string {
253	var out []string
254	for _, f := range strings.Fields(s) {
255		if strings.HasPrefix(f, "-") {
256			continue
257		}
258		f = strings.Trim(f, `"'`)
259		// A pin, an extra or a path is not a name the registry answers to.
260		if i := strings.IndexAny(f, "=<>[!~@"); i > 0 {
261			f = f[:i]
262		}
263		if f == "" || strings.ContainsAny(f, "/.$") && !strings.HasPrefix(f, "@") {
264			continue
265		}
266		out = append(out, strings.ToLower(f))
267	}
268	return out
269}
270
271// takesValue is the docker run flags whose value is a separate word, so the
272// token after one of them is not the image.
273var takesValue = map[string]bool{
274	"-p": true, "-v": true, "-e": true, "-u": true, "-w": true, "-h": true,
275	"--name": true, "--network": true, "--net": true, "--gpus": true,
276	"--restart": true, "--entrypoint": true, "--add-host": true, "--env": true,
277	"--volume": true, "--publish": true, "--user": true, "--workdir": true,
278	"--label": true, "--mount": true, "--device": true, "--memory": true,
279}
280
281// imageArg is the first word of a docker run line that is not a flag or a
282// flag's value. Matching the image with a regex means matching docker's whole
283// flag grammar, and it gets the container name instead about half the time.
284func imageArg(rest string) string {
285	fields := strings.Fields(rest)
286	for i := 0; i < len(fields); i++ {
287		f := fields[i]
288		if !strings.HasPrefix(f, "-") {
289			return f
290		}
291		if takesValue[f] {
292			i++
293		}
294	}
295	return ""
296}
297
298// dockerRepo normalises an image reference to what Docker Hub's API wants, and
299// drops anything hosted somewhere else since only Hub is being asked.
300func dockerRepo(ref string) string {
301	ref = strings.TrimSpace(ref)
302	if ref == "" || ref == "scratch" || strings.HasPrefix(ref, "$") {
303		return ""
304	}
305	// A build stage name, not an image.
306	if !strings.ContainsAny(ref, ":/") && !knownBareImage[ref] {
307		return ""
308	}
309	if i := strings.Index(ref, "@"); i > 0 {
310		ref = ref[:i]
311	}
312	name := ref
313	if i := strings.LastIndex(name, ":"); i > 0 && !strings.Contains(name[i:], "/") {
314		name = name[:i]
315	}
316	parts := strings.Split(name, "/")
317	switch len(parts) {
318	case 1:
319		return "library/" + parts[0]
320	case 2:
321		// A registry host in front means it is not on Hub.
322		if strings.Contains(parts[0], ".") {
323			return ""
324		}
325		return name
326	}
327	return ""
328}
329
330// knownBareImage is the small set of official images written with no tag, where
331// a bare word really is an image rather than a build stage.
332var knownBareImage = map[string]bool{
333	"alpine": true, "debian": true, "ubuntu": true, "python": true, "node": true,
334	"golang": true, "nginx": true, "redis": true, "postgres": true, "mysql": true,
335	"busybox": true, "ollama/ollama": true,
336}
337
338func registryHas(ctx context.Context, client *http.Client, d Dependency) (found, checked bool) {
339	var url string
340	switch d.Eco {
341	case "pypi":
342		url = "https://pypi.org/pypi/" + d.Name + "/json"
343	case "npm":
344		url = "https://registry.npmjs.org/" + d.Name
345	case "go":
346		url = "https://proxy.golang.org/" + goProxyEscape(d.Name) + "/@v/list"
347	case "docker":
348		url = "https://hub.docker.com/v2/repositories/" + d.Name + "/"
349	default:
350		return false, false
351	}
352
353	ctx, cancel := context.WithTimeout(ctx, depTimeout)
354	defer cancel()
355	req, err := http.NewRequestWithContext(ctx, "GET", url, nil)
356	if err != nil {
357		return false, false
358	}
359	req.Header.Set("User-Agent", browserUA)
360	resp, err := client.Do(req)
361	if err != nil {
362		return false, false
363	}
364	defer resp.Body.Close()
365	switch {
366	case resp.StatusCode == http.StatusOK:
367		return true, true
368	case resp.StatusCode == http.StatusNotFound:
369		return false, true
370	}
371	// A 403 or a 429 says the registry is not answering questions right now,
372	// which is not evidence the package is missing.
373	return false, false
374}
375
376// goProxyEscape is the proxy's own casing rule: an upper case letter becomes
377// !lower, since the protocol is case insensitive on disk.
378func goProxyEscape(path string) string {
379	var b strings.Builder
380	for _, r := range path {
381		if r >= 'A' && r <= 'Z' {
382			b.WriteByte('!')
383			b.WriteRune(r + 32)
384			continue
385		}
386		b.WriteRune(r)
387	}
388	return b.String()
389}
390
391// depWarnings names anything the registry says does not exist. A package that
392// could not be checked is left silent, since a warning nobody can act on is
393// worse than none.
394func depWarnings(deps []Dependency) []string {
395	var missing []string
396	for _, d := range deps {
397		if d.Checked && !d.Found {
398			missing = append(missing, fmt.Sprintf("%s (%s)", d.Name, ecoName(d.Eco)))
399		}
400	}
401	if len(missing) == 0 {
402		return nil
403	}
404	return []string{fmt.Sprintf(
405		"the code uses %s, which %s not there when checked, so the name is probably wrong",
406		strings.Join(missing, ", "),
407		map[bool]string{true: "was", false: "were"}[len(missing) == 1])}
408}
409
410func ecoName(eco string) string {
411	switch eco {
412	case "pypi":
413		return "PyPI"
414	case "npm":
415		return "npm"
416	case "go":
417		return "Go modules"
418	case "docker":
419		return "Docker Hub"
420	}
421	return eco
422}
423
424// nodeBuiltin is what node ships with, so an import of it is not a package.
425var nodeBuiltin = map[string]bool{
426	"assert": true, "buffer": true, "child_process": true, "cluster": true,
427	"console": true, "crypto": true, "dgram": true, "dns": true, "events": true,
428	"fs": true, "http": true, "http2": true, "https": true, "net": true,
429	"os": true, "path": true, "process": true, "querystring": true,
430	"readline": true, "stream": true, "string_decoder": true, "timers": true,
431	"tls": true, "tty": true, "url": true, "util": true, "v8": true, "vm": true,
432	"worker_threads": true, "zlib": true, "perf_hooks": true, "test": true,
433}
434
435// pyStdlib is the standard library as of 3.13, near enough. A name missing from
436// here costs one lookup that comes back found, which is the harmless direction.
437var pyStdlib = map[string]bool{
438	"abc": true, "argparse": true, "array": true, "ast": true, "asyncio": true,
439	"base64": true, "binascii": true, "bisect": true, "builtins": true, "bz2": true,
440	"calendar": true, "cmath": true, "cmd": true, "collections": true, "colorsys": true,
441	"concurrent": true, "configparser": true, "contextlib": true, "copy": true,
442	"csv": true, "ctypes": true, "dataclasses": true, "datetime": true, "decimal": true,
443	"difflib": true, "dis": true, "email": true, "enum": true, "errno": true,
444	"faulthandler": true, "filecmp": true, "fileinput": true, "fnmatch": true,
445	"fractions": true, "ftplib": true, "functools": true, "gc": true, "getopt": true,
446	"getpass": true, "gettext": true, "glob": true, "gzip": true, "hashlib": true,
447	"heapq": true, "hmac": true, "html": true, "http": true, "imaplib": true,
448	"importlib": true, "inspect": true, "io": true, "ipaddress": true, "itertools": true,
449	"json": true, "keyword": true, "linecache": true, "locale": true, "logging": true,
450	"lzma": true, "mailbox": true, "math": true, "mimetypes": true, "mmap": true,
451	"multiprocessing": true, "netrc": true, "numbers": true, "operator": true,
452	"os": true, "pathlib": true, "pickle": true, "pkgutil": true, "platform": true,
453	"plistlib": true, "poplib": true, "pprint": true, "profile": true, "pty": true,
454	"queue": true, "quopri": true, "random": true, "re": true, "readline": true,
455	"reprlib": true, "resource": true, "runpy": true, "sched": true, "secrets": true,
456	"select": true, "selectors": true, "shelve": true, "shlex": true, "shutil": true,
457	"signal": true, "site": true, "smtplib": true, "socket": true, "socketserver": true,
458	"sqlite3": true, "ssl": true, "stat": true, "statistics": true, "string": true,
459	"struct": true, "subprocess": true, "sys": true, "sysconfig": true, "tarfile": true,
460	"tempfile": true, "textwrap": true, "threading": true, "time": true, "timeit": true,
461	"tkinter": true, "token": true, "tokenize": true, "tomllib": true, "trace": true,
462	"traceback": true, "tracemalloc": true, "types": true, "typing": true,
463	"unicodedata": true, "unittest": true, "urllib": true, "uuid": true, "venv": true,
464	"warnings": true, "wave": true, "weakref": true, "webbrowser": true, "wsgiref": true,
465	"xml": true, "xmlrpc": true, "zipfile": true, "zipimport": true, "zoneinfo": true,
466}