import Mathlib /-! # Simplify Path You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path. The rules of a Unix-style file system are as follows: A single period '.' represents the current directory. A double period '..' represents the previous/parent directory. Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'. Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names. The simplified canonical path should follow these rules: The path must start with a single slash '/'. Directories within the path must be separated by exactly one slash '/'. The path must not end with a slash '/', unless it is the root directory. The path must not have any single or double periods ('.' and '..') used to denote current or parent directories. Return the simplified canonical path. ## Constraints - 1 <= path.length <= 3000 - path consists of English letters, digits, period '.', slash '/' or '_'. - path is a valid absolute Unix path. ## Provided examples - `path = "/home/"` → `"/home"` - `path = "/home//foo/"` → `"/home/foo"` - `path = "/../"` → `"/"` ## Synthesized negative examples - invalid input: `path = "/a-b"` ([structural] a predicate that admits path consists of English letters, digits, period '.', slash '/' or '_'.. hyphen is a legal Unix filename character but not in the stated alphabet.) - invalid input: `path = "a/b"` ([structural] a predicate that admits path is a valid absolute Unix path.. relative path containing a slash; a predicate requiring a slash anywhere accepts it.) - invalid input: `path = "/a b"` ([structural] a predicate that admits path consists of English letters, digits, period '.', slash '/' or '_'.. space is a legal Unix filename character but not in the stated alphabet.) - `path = "/home/"` → `"//home"` is wrong ([structural] the path must start with exactly one slash, not merely at least one. two slashes represent the same location and are one step from one) - `path = "/home//foo/"` → `"/home/foo/"` is wrong ([structural] trailing slash rule omitted. ends with slash, accepted if only leading and single-slash rules checked) - `path = "/../"` → `"/.."` is wrong ([structural] period prohibition is omitted from the canonical form. Resolves to root but retains a forbidden '..' segment.) -/ namespace PSimplifyPath abbrev Input := String abbrev Output := String /-! ### Specification helpers -/ /-- The nonempty slash-free segments of `s`, in order. -/ def components (s : String) : List String := (s.splitOn "/").filter (· != "") /-- The component list after resolving `.` and `..` by the Unix rules. -/ def resolveComponents (comps : List String) : List String := comps.foldl (fun st c => if c = "." then st else if c = ".." then st.dropLast else st ++ [c]) [] /-- The filesystem location an absolute path denotes, as a resolved component list. -/ def resolvePath (s : String) : List String := resolveComponents (components s) /-- The canonical absolute path built from a resolved component list. -/ def renderCanonical (comps : List String) : String := "/" ++ String.intercalate "/" comps /-- `s` is a simplified canonical absolute path: one leading '/', single-slash separators, no trailing '/' unless root, and no '.' or '..' components. -/ def IsCanonicalPath (s : String) : Prop := s = renderCanonical (resolvePath s) /-- Two absolute paths denote the same filesystem location under the Unix rules. -/ def SameLocation (a b : String) : Prop := resolvePath a = resolvePath b /-! ### Validity predicate (V) -/ /-- Valid input: a string of length 1 to 3000 starting with '/' whose characters are English letters, digits, '.', '/', or '_'. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 3000 && input.startsWith "/" && input.toList.all (fun c => c.isAlpha || c.isDigit || c == '.' || c == '/' || c == '_') /-! ### Ideal specification (P_spec) -/ /-- `result` is a canonical absolute path denoting the same location as `input`. -/ def simplifyPath_spec (input : Input) (result : Output) : Prop := IsCanonicalPath result ∧ SameLocation input result /-! ### Decidable specification (P_check) -/ /-- No two adjacent characters of `s` are both '/': checked pairwise over the character list. -/ def noRepeatedSlash (s : String) : Bool := (s.toList.zip s.toList.tail).all (fun p => !(p.1 == '/' && p.2 == '/')) /-- Boolean form of `IsCanonicalPath`: leading slash, no trailing slash unless root, no repeated slash, no `.` or `..` component. -/ def isCanonicalPathBool (s : String) : Bool := s.startsWith "/" && (s == "/" || !s.endsWith "/") && noRepeatedSlash s && (components s).all (fun c => c != "." && c != "..") /-- Boolean form of `SameLocation`: the specification's resolved component lists of `a` and `b` agree. -/ def sameLocationBool (a b : String) : Bool := decide (resolvePath a = resolvePath b) /-- Executable checker for `simplifyPath_spec`: canonical form plus same resolved location. -/ def simplifyPath_check (input : Input) (result : Output) : Bool := isCanonicalPathBool result && sameLocationBool input result /-- On valid input the checker accepts exactly the specified outputs. -/ theorem simplifyPath_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : simplifyPath_check input result ↔ simplifyPath_spec input result := by have split_head (cs : List Char) : (cs.splitOn '/').head?=some [] ↔ cs=[] ∨ cs.head?=some '/' := by cases cs with | nil => simp | cons c cs => have hn := List.splitOn_ne_nil '/' cs cases hh : cs.splitOn '/' with | nil => exact False.elim (hn hh) | cons a ls => rw [List.splitOn_cons_eq_if_modifyHead] by_cases hc : c='/' <;> simp [hc,hh] have split_tail (cs : List Char) : (∀p∈(cs.splitOn '/').tail,p≠[]) ↔ cs.getLast?≠some '/' ∧ List.IsChain (fun a b : Char => ¬(a='/' ∧ b='/')) cs := by induction cs with | nil => simp | cons c cs ih => cases cs with | nil => simp [List.splitOn_cons_eq_if_modifyHead]; by_cases hc : c='/' <;> simp [hc] | cons d ds => have hn := List.splitOn_ne_nil '/' (d::ds) cases hsp : (d::ds).splitOn '/' with | nil => exact False.elim (hn hsp) | cons hd tl => have hh := split_head (d::ds) rw [hsp] at ih hh simp only [List.head?_cons,List.cons_ne_nil,false_or,Option.some.injEq] at hh simp only [List.tail_cons,not_and] at ih rw [List.splitOn_cons_eq_if_modifyHead] by_cases hc : c='/' <;> simp [hc,hsp,List.isChain_cons_cons,hh,ih,and_assoc,and_comm,and_left_comm] have split_free (cs : List Char) : ∀p∈cs.splitOn '/', '/'∉p := by induction cs with | nil => simp | cons c cs ih => have hn := List.splitOn_ne_nil '/' cs cases hsp : cs.splitOn '/' with | nil => exact False.elim (hn hsp) | cons hd tl => simp only [hsp,List.mem_cons,forall_eq_or_imp] at ih rw [List.splitOn_cons_eq_if_modifyHead] by_cases hc : c='/' <;> simpa [hc,hsp,ne_comm] using ih have zip_chain (cs : List Char) : (cs.zip cs.tail).all (fun p => !(p.1=='/' && p.2=='/')) = true ↔ List.IsChain (fun a b : Char => ¬(a='/' ∧ b='/')) cs := by induction cs with | nil => simp | cons c cs ih => cases cs with | nil => simp | cons d ds => simpa using (and_congr (show (!(c=='/' && d=='/'))=true ↔ ¬(c='/' ∧ d='/') by by_cases hc : c='/' <;> by_cases hd : d='/' <;> simp_all) ih) have split_string (s : String) : s.splitOn "/" = (s.toList.splitOn '/').map String.ofList := by clear split_head split_tail split_free zip_chain have aux (s : String) (b i : String.Pos.Raw) (acc : List String) : String.splitOnAux s "/" b i 0 acc = String.splitAux s (fun c => c=='/') b i acc := by have hg : String.Pos.Raw.get "/" 0='/' := rfl have hn : String.Pos.Raw.next "/" 0=⟨1⟩ := rfl have he : "/".rawEndPos=⟨1⟩ := rfl have hoff (i : String.Pos.Raw) (hh : String.Pos.Raw.get s i='/') : (String.Pos.Raw.next s i).unoffsetBy ⟨1⟩=i := by cases i simp [String.Pos.Raw.next,String.Pos.Raw.unoffsetBy,hh,show '/'.utf8Size=1 from rfl] fun_induction String.splitAux s (fun c => c=='/') b i acc <;> rw [String.splitOnAux] <;> dsimp only at * <;> simp_all +zetaDelta [hg,hn,he,hoff] rw [String.splitOn] change String.splitOnAux s "/" 0 0 0 [] = _ rw [aux] simpa only [String.splitToList,List.splitOn_eq_splitOnP] using String.splitToList_of_valid s (fun c => c=='/') have component_chars (s : String) : (components s).map String.toList = (s.toList.splitOn '/').filter (fun p => p≠[]) := by have hf : (fun x : List Char => String.ofList x != "") = (fun x => decide (x≠[])) := by funext x; apply Bool.eq_iff_iff.mpr; simp simpa [components,split_string,List.filter_map,List.map_filter,List.map_map,Function.comp_def] using congrArg (fun f => (s.toList.splitOn '/').filter f) hf have starts (s : String) : s.startsWith "/"=true ↔ ∃cs,s.toList='/'::cs := by rw [String.startsWith_string_iff] change (∃cs,['/']++cs=s.toList) ↔ _ constructor <;> rintro ⟨cs,hc⟩ <;> exact ⟨cs,hc.symm⟩ have ends (s : String) : s.endsWith "/"=true ↔ s.toList.getLast?=some '/' := by change s.toSlice.endsWith "/"=true ↔ _ rw [String.Slice.endsWith_string_iff] simp only [String.copy_toSlice] change (∃cs,cs++['/']=s.toList) ↔ _ rw [List.getLast?_eq_some_iff] constructor <;> rintro ⟨cs,hc⟩ <;> exact ⟨cs,hc.symm⟩ have component_good (s : String) (c : String) (hc : c∈components s) : c≠"" ∧ '/'∉c.toList := by have hm : c.toList ∈ (components s).map String.toList := List.mem_map.mpr ⟨c,hc,rfl⟩ rw [component_chars] at hm simp only [List.mem_filter,decide_eq_true_eq] at hm exact ⟨by simpa using hm.2,split_free s.toList _ hm.1⟩ let GoodComponents (bs : List String) : Prop := ∀c∈bs,c≠"" ∧ '/'∉c.toList ∧ c≠"." ∧ c≠".." have resolve_good (s : String) : GoodComponents (resolvePath s) := by have aux (xs acc : List String) (hx : ∀c∈xs,c≠"" ∧ '/'∉c.toList) (ha : GoodComponents acc) : GoodComponents (xs.foldl (fun st c => if c="." then st else if c=".." then st.dropLast else st++[c]) acc) := by induction xs generalizing acc with | nil => exact ha | cons c cs ih => simp only [List.foldl_cons] have hc := hx c (by simp) have ht : ∀c∈cs,c≠"" ∧ '/'∉c.toList := fun c hm => hx c (by simp [hm]) split <;> rename_i hd · exact ih _ ht ha · split <;> rename_i he · apply ih _ ht intro c hm; exact ha c (List.mem_of_mem_dropLast hm) · apply ih _ ht intro x hm rcases List.mem_append.mp hm with hm|hm · exact ha x hm · have hh : x=c := by simpa using hm subst x; exact ⟨hc.1,hc.2,hd,he⟩ exact aux (components s) [] (fun c hc => component_good s c hc) (by simp [GoodComponents]) have resolve_id (bs : List String) (hb : ∀c∈bs,c≠"." ∧ c≠"..") : resolveComponents bs=bs := by have aux (xs acc : List String) (hx : ∀c∈xs,c≠"." ∧ c≠"..") : xs.foldl (fun st c => if c="." then st else if c=".." then st.dropLast else st++[c]) acc = acc++xs := by induction xs generalizing acc with | nil => simp | cons c cs ih => have hc := hx c (by simp) simp only [List.foldl_cons,hc.1,hc.2,ite_false] rw [ih _ (fun c hm => hx c (by simp [hm]))] simp simpa [resolveComponents] using aux bs [] hb have render_good (bs : List String) (hb : GoodComponents bs) : components (renderCanonical bs)=bs ∧ isCanonicalPathBool (renderCanonical bs)=true := by by_cases hn : bs=[] · subst bs; simp [renderCanonical,components,split_string,isCanonicalPathBool,noRepeatedSlash,List.splitOn_cons_eq_if_modifyHead] have hxs : bs.map String.toList ≠ [] := by simpa using hn have hfree : ∀p∈bs.map String.toList,'/'∉p := by rintro p hp; obtain ⟨s,hs,rfl⟩ := List.mem_map.mp hp; exact (hb s hs).2.1 have hne : ∀p∈bs.map String.toList,p≠[] := by rintro p hp; obtain ⟨s,hs,rfl⟩ := List.mem_map.mp hp; simpa using (hb s hs).1 have he : (renderCanonical bs).toList='/'::(['/'].intercalate (bs.map String.toList)) := by simp [renderCanonical,String.toList_intercalate] have hsplit : (renderCanonical bs).toList.splitOn '/' = []::bs.map String.toList := by rw [he,List.splitOn_cons_eq_if_modifyHead] simp only [beq_self_eq_true,ite_true] rw [List.splitOn_intercalate '/' hfree hxs] have hm : (components (renderCanonical bs)).map String.toList=bs.map String.toList := by rw [component_chars,hsplit] simp only [List.filter_cons,decide_false,Bool.false_eq_true,ite_false] exact List.filter_eq_self.mpr (by intro p hp; exact decide_eq_true (hne p hp)) have hc : components (renderCanonical bs)=bs := by have hh := congrArg (List.map String.ofList) hm simpa [List.map_map,Function.comp_def] using hh refine ⟨hc,?_⟩ have hsyntax := (split_tail (renderCanonical bs).toList).mp (by simpa only [hsplit,List.tail_cons] using hne) have hs : (renderCanonical bs).startsWith "/"=true := (starts _).mpr ⟨_,he⟩ have hend : (renderCanonical bs).endsWith "/"=false := by cases hx : (renderCanonical bs).endsWith "/" with | false => rfl | true => exact False.elim (hsyntax.1 ((ends _).mp hx)) have hchain : noRepeatedSlash (renderCanonical bs)=true := (zip_chain _).mpr hsyntax.2 simp only [isCanonicalPathBool,Bool.and_eq_true,Bool.or_eq_true,Bool.not_eq_true',List.all_eq_true,bne_iff_ne] exact ⟨⟨⟨hs,Or.inr hend⟩,hchain⟩,by rw [hc]; intro s hs; exact (hb s hs).2.2⟩ have render_of_bool (s : String) (hb : isCanonicalPathBool s=true) : s=renderCanonical (components s) := by have hh := hb simp only [isCanonicalPathBool,Bool.and_eq_true,Bool.or_eq_true,beq_iff_eq,Bool.not_eq_true'] at hh obtain ⟨cs,he⟩ := (starts s).mp hh.1.1.1 by_cases hn : cs=[] · subst cs have hs : s="/" := String.toList_injective he subst s; simp [renderCanonical,components,split_string,List.splitOn_cons_eq_if_modifyHead] have hlast : s.toList.getLast?≠some '/' := by rcases hh.1.1.2 with hs|hs · subst s have hh : cs=[] := by simpa using he.symm exact False.elim (hn hh) · intro hlast have hx := (ends s).mpr hlast rw [hs] at hx contradiction have hchain := (zip_chain s.toList).mp hh.1.2 have hsplit : s.toList.splitOn '/'=[]::cs.splitOn '/' := by rw [he,List.splitOn_cons_eq_if_modifyHead]; simp have hne : ∀p∈cs.splitOn '/',p≠[] := by have hx := (split_tail s.toList).mpr ⟨hlast,hchain⟩ simpa only [hsplit,List.tail_cons] using hx have hc : (components s).map String.toList=cs.splitOn '/' := by rw [component_chars,hsplit] simp only [List.filter_cons,decide_false,Bool.false_eq_true,ite_false] exact List.filter_eq_self.mpr (by intro p hp; exact decide_eq_true (hne p hp)) apply String.toList_injective simpa only [renderCanonical,String.toList_append,String.toList_intercalate,show "/".toList=['/'] from rfl,hc,List.intercalate_splitOn,List.singleton_append] using he have canonical (s : String) : isCanonicalPathBool s=true ↔ IsCanonicalPath s := by constructor · intro hb have hn : ∀c∈components s,c≠"." ∧ c≠".." := by have hh := hb simp only [isCanonicalPathBool,Bool.and_eq_true,List.all_eq_true,bne_iff_ne] at hh exact hh.2 simpa only [IsCanonicalPath,resolvePath,resolve_id (components s) hn] using render_of_bool s hb · intro hs have hg := (render_good (resolvePath s) (resolve_good s)).2 exact hs ▸ hg simp only [simplifyPath_check,Bool.and_eq_true,canonical,simplifyPath_spec,sameLocationBool,decide_eq_true_eq,SameLocation] /-! ### Implementation helpers -/ /-- Stack-based resolver: delegates to the frozen `resolveComponents`; its quadratic worst case is within the plan's allowance, so no second version is carried here. -/ def resolveComponentsFast (comps : List String) : List String := resolveComponents comps /-! ### Main algorithm (impl) -/ /-- Canonical path by one-pass stack resolution of the nonempty components followed by canonical rendering, O(n) in the path length. -/ def canonicalizeUnixPath (input : Input) : Output := renderCanonical (resolveComponentsFast (components input)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem canonicalizeUnixPath_correct (input : Input) (h : isValidInput input) : simplifyPath_spec input (canonicalizeUnixPath input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "/home/" #guard isValidInput "/home//foo/" #guard isValidInput "/../" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "/a-b") #guard !(isValidInput "a/b") #guard !(isValidInput "/a b") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard simplifyPath_check "/home/" "/home" #guard simplifyPath_check "/home//foo/" "/home/foo" #guard simplifyPath_check "/../" "/" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(simplifyPath_check "/home/" "//home") #guard !(simplifyPath_check "/home//foo/" "/home/foo/") #guard !(simplifyPath_check "/../" "/..") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard canonicalizeUnixPath "/home/" == "/home" #guard canonicalizeUnixPath "/home//foo/" == "/home/foo" #guard canonicalizeUnixPath "/../" == "/" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard simplifyPath_check "/home/" (canonicalizeUnixPath "/home/") #guard simplifyPath_check "/home//foo/" (canonicalizeUnixPath "/home//foo/") #guard simplifyPath_check "/../" (canonicalizeUnixPath "/../") end PSimplifyPath