Changeset 2739

Timestamp:

08/25/08 07:23:17 (15 months ago)

Author:

black

Message:

Next iteration of CordedStrings?, with substring nodes. Comparison of Strings with substring nodes is a work in progress. This commit fixes bugs in the Range comparison code that were impeding that progress

Location:

trunk

Files:

• Library/CordedString.fsi (modified) (1 diff)
• Library/CordedString.fss (modified) (7 diffs)
• Library/FortressLibrary.fsi (modified) (6 diffs)
• Library/FortressLibrary.fss (modified) (11 diffs)
• Library/JavaString.fss (modified) (4 diffs)
• ProjectFortress/not_passing_yet/CordedStringTests.fss (modified) (5 diffs)
• ProjectFortress/tests/RangeTest.fss (modified) (1 diff)

trunk/Library/CordedString.fsi

@@ -24 +24 @@
   end
   
+  trait SubString extends String
+    comprises {...}
+  end 
+  
   margin(prefix: String, indent: ZZ32)
 

trunk/Library/CordedString.fss

@@ -17 +17 @@
 
 component CordedString
+import List.{...}
 export CordedString
 
 (* I believe that these should eventually go with the range code. *)
-
     (*Intersection of two ranges *)
-    opr ∩ (r0: Range[\ZZ32\], r1: Range[\ZZ32\]) = (r0.lower MAX r1.lower) : (r0.upper MIN r1.upper) 
+    opr ∩ (r0: Range⟦ZZ32⟧, r1: Range⟦ZZ32⟧) = (r0.lower MAX r1.lower) : (r0.upper MIN r1.upper) 
+      
+  test rangeIntersect() = do
+        assert((0:5) ∩ (0:3), 0:3)
+        assert((0:5) ∩ (3:7), 3:5)
+        assert((0:5) ∩ (7:10), 7:5)
+        assert((5:3).size, 0, "The size of 5:3 is not zero!")
+        assert((9:8).size, 0, "The size of 9:8 is not zero!")
+        assert( (5:3).isEmpty, "5:3 is not empty!")
+        assert( (9:8).isEmpty, "9:8 is not empty!")
+        assert( ((0:5) ∩ (7:10)).isEmpty, "0:5 has a non-empty intersection with 7:10 !")
+        assert( (7:9)≪7, (0#3), "7:9≪7 isn't 0#3" ) 
+  end
+  
     (* Shift a range left by the specified amount.  *)
-    opr ↙(r: Range[\ZZ32\], leftShift: ZZ32) = (r.lower - leftShift)#r.extent
-
+    opr ≪(r: Range⟦ZZ32⟧, leftShift: ZZ32) = (r.lower - leftShift)#r.extent
+    (* Shift a range right by the specified amount. *)
+    opr ≫(r: Range⟦ZZ32⟧, rightShift: ZZ32) = (r.lower + rightShift)#r.extent
+    
+  test testShiftLeft(): () = do
+    assert( (10:12) ≪ 9, 1:3)
+  end
+  
+  test testShiftRight(): () = do
+    assert( (2:3) ≫ 5, 7:8)
+  end
+  
+  test testRangeContainment = do
+    assert( (2:3) ≤ (2:3), "(2:3) not less than or equal to (2:3)")
+    (* println "(2#2) CMP (2:3) = " ((2#2) CMP (2:3))  *)
+    assert( (2#2) ≤ (2:3), "(2#2) not less than or equal to (2:3)")
+  end
+(* 
+==== Shared Traits ====
+*)
+
+  trait Concatenable extends String
+    opr || (self, other:String): String = 
+        if |other| = 0 then self else CatString(self, other) end
+    opr || (self, _:EmptyString): String = self
+    opr || (self, other:Char) = CatString(self, other.toString)
+  end
 (*
 ==== CatString ====
 *)
 
-  object CatString(left: String, right:String)  extends String
+  object CatString(left: String, right:String)  extends {String, Concatenable}
     size = left.size + right.size
     depthField = 1 + (left.depth MAX right.depth)
@@ -49 +87 @@
         if i ∈ left.indices then left[i] else right[i - |left|] end
 
-    opr[r0:Range[\ZZ32\]] : String =  do
+    opr[r0:Range⟦ZZ32⟧] : String =  do
         r1 = self.bounds[r0]     (* This will complete r0 if it is incomplete, and throw a bounds exception when necessary *)
-        self.uncheckedSubstring(r1)
+        if r1.isEmpty then 
+            EmptyString 
+        else 
+            self.uncheckedSubstring(r1)
+        end
       end
       
@@ -65 +107 @@
         right.showStructure(indent+8)
     end
-      
-    uncheckedSubstring(r0: Range⟦ZZ32⟧) = do
-        r1 = (r0 ↙ left.size)
+
+(* without SubString nodes: 
+      
+    uncheckedSubstring(r0: Range⟦ZZ32⟧) = do
+        r1 = (r0 ≪ left.size)
         left.uncheckedSubstring(r0 ∩ left.bounds) || right.uncheckedSubstring(r1 ∩ right.bounds)            
       end
-      
-      
-(* Here is the three-way version: this framework is better once we have subString nodes
- 
-    uncheckedSubstring(r0: Range[\ZZ32\]) = do
+ *)
+            
+    uncheckedSubstring(r0: Range⟦ZZ32⟧) = do
         leftBounds' = r0 ∩ left.bounds
-        r1 = (r0 ↙ left.size)
+        r1 = (r0 ≪ left.size)
         rightBounds' = r1 ∩ right.bounds
-        if leftBounds.isEmpty then right.uncheckedSubstring(rightBounds')
-        else if rightBounds.isEmpty then left.uncheckedSubstring(leftBounds')
-        else left.uncheckedSubstring(leftBounds') || right.uncheckedSubstring(rightBounds')            
-      end  
- *)
-      
-
-    opr || (self, other:String): String = 
-        if |other| = 0 then self else CatString(self, other) end
-    opr || (self, _:EmptyString) = self
-    opr || (self, other:Char) = CatString(self, other.toString)
-    
+(*        atomic do 
+            println "uncheckedSubstring " r0 " of "
+            self.showStructure()
+            println "==============="
+            println "leftBounds' = " leftBounds' ( if leftBounds'.isEmpty then "(empty)" else "(non-empty)" end )
+            println "rightBounds' = " rightBounds'  ( if rightBounds'.isEmpty then "(empty)" else "(non-empty)" end )
+            println "==============="
+        end  *)
+        if leftBounds'.isEmpty then 
+            right.uncheckedSubstring(rightBounds')
+        elif rightBounds'.isEmpty then
+            left.uncheckedSubstring(leftBounds')
+        else
+            SubString'(self, r0)
+        end       
+    end  
+
     println(self): () = do print(left) ; println(right) end  
     print(self): () = do print(left) ; print(right) end
-
-  end
-
-  object ConcatGenerator[\T\](first:Generator[\T\], second:Generator[\T\])
-        extends Generator[\T\]
-    generate[\R\](r: Reduction[\R\], body:T->R):R =
-        r.join(first.generate[\R\](r, body), second.generate[\R\](r, body))
+    
+    subdivide(): Maybe⟦Generator⟦(ZZ32, String)⟧⟧ = Just ⟨ (0, left), (|left|, right) ⟩
+
+  end
+
+  object ConcatGenerator⟦T⟧(first:Generator⟦T⟧, second:Generator⟦T⟧)
+        extends Generator⟦T⟧
+    generate⟦R⟧(r: Reduction⟦R⟧, body:T->R):R =
+        r.join(first.generate⟦R⟧(r, body), second.generate⟦R⟧(r, body))
   end
 
@@ -105 +154 @@
 *)
 
-  value object EmptyString extends String
+  value object EmptyString extends {String, Concatenable}
     getter size() = 0
     getter bounds() = 0#0
     getter isEmpty() = true
-    getter generator() = Nothing[\Char\]
+    getter generator() = Nothing⟦Char⟧
     opr CMP(self, other: String) =
         |self| CMP |other|
@@ -116 +165 @@
     get(i): Char = fail("Can't get characters from an empty string")
 
-    opr[r: Range[\ZZ32\]] : String = do
+    opr[r: Range⟦ZZ32⟧] : String = do
         rr = self.indices[r]     (* to raise a bounds error *)
         EmptyString
@@ -137 +186 @@
 
     opr || (self, other:String): String = other
-(*    opr || (other: String, self): String = other   *)    (* this optimizes the case with EmptyString on the right*)
-    opr || (self, _: EmptyString): String = self
     opr || (self, other:Char) = other.toString
       
@@ -145 +192 @@
   
   end
-
-  run(args: String...): () = do println "Finished" end 
-  
-  test rangeIntersect() = do
-        assert((0:5) ∩ (0:3), 0:3)
-        assert((0:5) ∩ (3:7), 3:5)
-        assert((0:5) ∩ (7:10), 7:5)
-        deny(5:3, 9:8)                  (* I hoped that that this would be an assert! *)
-        assert((5:3).size, 0, "The size of 5:3 is not zero!")
-        assert((9:8).size, 0, "The size of 9:8 is not zero!")
-        assert( (5:3).isEmpty, "5:3 is not empty!")
-        assert( (9:8).isEmpty, "9:8 is not empty!")
-        assert( ((0:5) ∩ (7:10)).isEmpty, "0:5 has a non-empty intersection with 7:10 !")
+  
+  subdivide() = Nothing⟦Generator⟦(ZZ32, String)⟧⟧
+
+(*
+==== SubString ====
+*)
+  trait SubString extends {String, Concatenable}
+    comprises {SubString'}
+  end 
+  
+  object SubString'(parent: String, range: Range⟦ZZ32⟧) extends SubString
+    getter size() = range.size
+    getter depth() = parent.depth       (* Why not one more than the parent?  Would this break the balancing invariant? *)
+    getter isEmpty() = false
+    
+    opr CMP(self, other: String) =  do
+ (*       if pgen ← parent.subdivide() then
+            BIG LEXICO [(start, str) ← pgen] self.uncheckedSubstring((start#|str|) ∩ self.bounds) CMP str
+        else
+*)
+            (BIG LEXICO [i ← 0#(|self| MIN |other|)] self.get(i) CMP other.get(i)) LEXICO (|self| CMP |other|)               
+(*        end
+*)
+    end
+    
+    
+    verify() = do
+        parent.verify()
+        deny(range.isEmpty, "SubString (" range ") has empty range")
+        assert(range < parent.bounds, "SubString (" range ") has range equal to or greater than that of parent (" parent.bounds ")") 
+    end
+    showStructure(indent) = do
+        margin(indent)
+        println "S" |self| "=[" range "]" 
+        parent.showStructure(indent + 8)
+    end
+    
+    get(i:ZZ32) = do
+      assert(i < range.size, "getting char " i " from a substring of size " |range|)
+      parent.get(range.lower+i)
+    end
+    
+    uncheckedSubstring(r0: Range⟦ZZ32⟧) = do
+        assert((r0≫range.lower) ≤ range, "asking for substring ["  r0 "] of S" self.size)
+        if r0.isEmpty then EmptyString
+        elif r0 = self.bounds then println "trivial substring"; self
+        else SubString'(parent, r0≫range.lower)
+        end
+    end
+    
+    println(self): () = do print(self) ; println() end  
+    print(self): () = for ch ← seq(self) do print ch end
+          
+    subdivide(): Maybe⟦Generator⟦(ZZ32, String)⟧⟧ = do
+    (* The pairs (start, str) that are generated are such that start[0] = 0 and start[i] = | str[0] || ... || str[i-1] |
+      and str[0] || str [1] || ... || str[n] = self
+    *)
+        pieces = parent.subdivide()
+        offset = range.lower
+        if pgen ← pieces then
+            <| if (start#piece.size) ≤ range then
+                    (start-offset, piece)
+                else 
+                    range' = range ∩ (start#piece.size)
+                    (range'.lower-offset, SubString'(piece, range'≪start))
+                end | (start, piece) ← pgen,   (range ∩ (start#piece.size)).nonEmpty |>
+        else
+            Nothing⟦Generator⟦(ZZ32,String)⟧⟧
+        end                    
+    end
   end
   

trunk/Library/FortressLibrary.fsi

@@ -99 +99 @@
     isLeftZero(_:Comparison): Boolean
 end
+
+opr BIG LEXICO(): BigReduction[\TotalComparison, TotalComparison\]
 
 trait Comparison
@@ -701 +703 @@
 trait Condition[\E\] extends SequentialGenerator[\E\]
     getter isEmpty(): Boolean
+    getter nonEmpty(): Boolean
     getter holds(): Boolean
     getter size(): ZZ32
@@ -973 +976 @@
         defined as %|self| = 0%. *)
     getter isEmpty(): Boolean
+    getter nonEmpty(): Boolean
     (** %size()% is depracted; use %|self|% instead. *)
     abstract getter size(): ZZ32
@@ -1802 +1806 @@
                 RangeWithExtent[\T\], PartialRange[\T\] }
     excludes { Number }
-
-    getter isEmpty(): Boolean
+   
     opr =(self,_:Range[\T\]): Boolean
 end
@@ -1969 +1972 @@
     opr |self| : ZZ32
     opr CASE_INSENSITIVE_CMP(self, other:String): TotalComparison
+    
     opr [i:ZZ32]: Char
     (** As a convenience, we permit LowerRange indexing to go 1 past the bounds
@@ -1978 +1982 @@
          should be in a "friends" interface *)
     uncheckedSubstring(r0: Range[\ZZ32\]) : String
+    
+    subdivide(): Maybe[\Generator[\(ZZ32, String)\]\]
 
     (** The operator %||% with at least one String argument converts to string and

trunk/Library/FortressLibrary.fss

@@ -135 +135 @@
     isLeftZero(_:Comparison): Boolean = true
 end
+
+opr BIG LEXICO(): BigReduction[\TotalComparison, TotalComparison\] =
+  BigReduction[\TotalComparison,TotalComparison\](LexicographicReduction)
+  
 
 trait Comparison
@@ -1100 +1104 @@
 trait Condition[\E\] extends { ZeroIndexed[\E\], SequentialGenerator[\E\] }
     getter isEmpty(): Boolean = NOT holds()
+    getter nonEmpty(): Boolean = NOT isEmpty()
     getter holds(): Boolean = cond[\Boolean\](fn (_:E):Boolean => true, fn () => false)
     getter size(): ZZ32 = if holds() then 1 else 0 end
@@ -1453 +1458 @@
         defined as size=0 *)
     getter isEmpty(): Boolean = |self| = 0
-    (** %size()% is depracated; use %|self|%. *)
+    getter nonEmpty(): Boolean = NOT self.isEmpty
+    (** %self.size% is equivalent to %|self|%. *)
     getter size(): ZZ32
     (** bounds() yields a range of indices that are valid for the
@@ -3027 +3033 @@
                 RangeWithExtent[\T\], PartialRange[\T\] }
     excludes { Number }
-    getter isEmpty(): Boolean = (|self| ≤ 0)
+    
     opr[r:Range[\T\]]: Range[\T\] = fail("Unrecognized Range " r)
     opr[_:OpenRange[\Any\]] : Range[\T\] = self
@@ -3284 +3290 @@
             self.lower#r.extent
         else
-            fail(self "[" r "] is not sufficiently large in some dimension")
+            fail(self "[" r "] is too small in some dimension")
         end
     opr[r:CompleteRange[\T\]]: CompleteRange[\T\] =
@@ -3303 +3309 @@
 
     opr =(self, other:CompleteRange[\T\]): Boolean =
-        self.isBounded=other.isBounded AND self.lower=other.lower AND
-        self.extent = other.extent
+    (*    isBounded()=other.isBounded() AND 
+         APB 2008.08.20: this seems bogus: isBounded tells us only whether we were created 
+         using an extent or an upper bound, and should not effect the comparison *)
+         lower()=other.lower() AND extent() = other.extent()    
+         
     opr CMP(self, other:Range[\T\]): Comparison =
         typecase other of
@@ -3315 +3324 @@
                     (LessThan,LessThan) => Unordered
                     (GreaterThan,GreaterThan) => Unordered
-                    (EqualTo,EqualTo) =>
+    (*  This case seems unncessary; the (EqualTo,Comparison) case will cover us    --- APB  2008.08.20
+                    (EqualTo,EqualTo) => EqualTo
                         if self.isBounded = other.isBounded then
                             EqualTo
@@ -3321 +3331 @@
                             Unordered
                         end
+   *)
                     (EqualTo,Comparison) => b
                     (GreaterThan,Comparison) => LessThan
@@ -3676 +3687 @@
      
     opr |self| : ZZ32 = self.size
-    opr CASE_INSENSITIVE_CMP(self, other:String): TotalComparison
-    (** As a convenience, we permit LowerRange indexing to go 1 past the bounds
+       
+    opr CASE_INSENSITIVE_CMP(self, other:String): TotalComparison =
+      ((BIG LEXICO[i <- 0#(|self| MIN |other|) ] self.get(i) CASE_INSENSITIVE_CMP other.get(i)) LEXICO (|self| CMP |other|))
+    
+    opr CMP(self, other:String): TotalComparison =
+      ((BIG LEXICO[i <- 0#(|self| MIN |other|) ] self.get(i) CMP other.get(i)) LEXICO (|self| CMP |other|))
+      
+    opr [i:ZZ32]: Char =
+        (** As a convenience, we permit LowerRange indexing to go 1 past the bounds
         of the String, returning the empty String, in order to permit some convenient
         String-trimming idioms. **)
-    opr [i:ZZ32]: Char =
         if 0 <= i < |self|
         then self.get(i)
@@ -3773 +3790 @@
 
 
-print(a:Any):() = print("" a)
-println(a:Any):() = println("" a)
+print(a:Any):() = print(a.toString)
+println(a:Any):() = println(a.toString)
 (* 0-argument versions handle passing of () to single-argument versions. *)
 print():() = print("")
@@ -3782 +3799 @@
 println(a: JavaString): () = 
         builtinPrimitive("com.sun.fortress.interpreter.glue.prim.StringPrim$Println")
-
 
 forDigit(x:ZZ32, radix:ZZ32): Maybe[\Char\] =

trunk/Library/JavaString.fss

@@ -33 +33 @@
     opr |self| : ZZ32 =
         builtinPrimitive("com.sun.fortress.interpreter.glue.prim.JavaString$Size")
+        
     uncheckedSubstring(r1: Range[\ZZ32\]) : String =
+    (* We could build a subString node here, but not until everything is working, because that will intorduce 
+       SubString objects into code that may still expect JavaStrings *)
         if r1.isEmpty then ""
         else self.javaSubstr(r1.lower, r1.upper + 1)    (* Java substr's endIndex is one past the last character *)
         end
+        
     opr =(self, other:String): Boolean =
         builtinPrimitive("com.sun.fortress.interpreter.glue.prim.JavaString$Eq")
@@ -66 +70 @@
         
     (* The following are curently dead code; see lines 3765 ish in FortressLibrary.fss *)    
+(*
     javaPrint(a: JavaString): () = 
         builtinPrimitive("com.sun.fortress.interpreter.glue.prim.StringPrim$Print")
     javaPrintln(a: JavaString): () = 
         builtinPrimitive("com.sun.fortress.interpreter.glue.prim.StringPrim$Println")
+*)
 
     indexOf(c:Char): Maybe[\ZZ32\] = do
@@ -101 +107 @@
 
     opr ||(self, b:String):String =
-        CatString(self, b)
-    (*  This makes the overloading resolution go beserk ...
-    opr ||(self, b:EmptyString):String = self
-    *)
+    (* It would be good to do something more sophisticated when b is short, such as copying
+       self and b into a StringBuffer and then turning the whole thing into a JavaString *)
+        if self.isEmpty then b else CatString(self, b) end
+        
+  
     opr ||(self, b:Char): String =
         if |self| ≥ flatStringInfo.maxSize then
@@ -111 +118 @@
             javaAppend(self, b)
         end
+        
+    subdivide() = Nothing[\Generator[\(ZZ32, String)\]\]
 
   end

trunk/ProjectFortress/not_passing_yet/CordedStringTests.fss

@@ -18 +18 @@
 component CordedStringTests
   import CordedString.{...}
+  import JavaString.{...}
   import Set.{...}
   import List.{...}
@@ -45 +46 @@
     end
   end
-  
+ 
   test subString(): () = do
     words = ⟨"The", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog."⟩
@@ -56 +57 @@
         assert(testString[i:j], referenceString[i:j]) 
     end
-
   end
-
+  
+  test subStringSimplification():() = do
+    testString = catStringFrom("The", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog.")
+    testString.verify()
+    sub1 = testString[34:36]
+    typecase sub1 of
+        JavaString => assert(true)
+        String => do sub1.showStructure()
+                            assert(false, "sub1=" sub1 " is not a JavaString") end
+     end
+  end
+  
+  (* test *) validateSubdivision(subject: String, division: Maybe⟦Generator⟦(ZZ32, String)⟧⟧): () = do
+    var len: ZZ32 = 0
+    var accum: String = ""
+    if gen ← division then 
+      for (start, str) ← seq(gen) do
+         assert(start, len, str)
+         len := len + |str|
+         accum := accum || str
+      end
+      assert(len, |subject|)
+      assert(accum, subject)
+    end
+  end
+    
+  test testSubdivide():() = do
+    subject = CatString("abcd", "efgh")
+    substr1 = subject[2:6]
+    var len: ZZ32 = 0
+    var accum: String = ""
+    for (start, str) ← seq(substr1.subdivide()) do
+         assert(start, len, str)
+         len := len + |str|
+         accum := accum || str
+    end
+    assert(len, |substr1|)
+    accum.verify()
+    accum.showStructure()
+    assert(accum, substr1)  
+    
+    substr2 = subject[4:6]
+    assert(substr2.subdivide(), Nothing⟦Generator⟦(ZZ32,String)⟧⟧)
+    
+    substr3 = subject[0:5]
+    for p ← seq(substr1.subdivide()) do
+        println ("found tuple" || p)    (* This should (did?) work prefix string too *)
+    end
+    
+  end 
+  
+(*
+  test comparison():() = do
+    smaller = catStringFrom("The", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog.")
+    bigger = catStringFrom("The", "quick", "brown", "jumped", "fox", "over", "the", "lazy", "doggie.")
+    smaller.verify
+    bigger.verify
+    smaller.showStructure
+    bigger.showStructure
+    assert(smaller < bigger)
+    assert(smaller[10:] < bigger[10:])
+    a = smaller[30:36] 
+    b = bigger[30:36]
+    a.verify
+    b.verify
+    a.showStructure
+    b.showStructure
+    assert(smaller[30:36] = bigger[30:36], smaller[30:36] " is not = to " bigger[30:36])
+  end
+ *)
+  object CatStringReduction extends MonoidReduction[\String\]
+    getter toString() = "CatStringReduction"
+    empty(): String = EmptyString
+    join(a:String, b:String):String = CatString(a, b)
+  end
+  
+  test catStringFrom(args: String...): String =
+    seq(args).generate⟦String⟧(CatStringReduction, fn(x) => x)
+  
+ 
   test testNonEmptyConcat(): () =  do
     stuff = "Hello "
@@ -66 +145 @@
     assert(hw, "Hello World")
     assert(hw, CatString("Hell", "o World"))
-    assert(hw[2:7], "llo Wo")
-    assert(hw[0:3], "Hell")
-    assert(hw[5:2], "")
   end
   
@@ -106 +182 @@
     for i ← result.bounds do assert(result[i] , chars[i]) end
   end  
-
+  
   run(args:String...):() = do
     println "Tests complete"

trunk/ProjectFortress/tests/RangeTest.fss

@@ -131 +131 @@
     chkOrder(mm,i,LessThan), i <- <|lm,lh',lh,mh|>
     chkOrder(mm,hh,Unordered)
-    chkOrder(lh,lh',Unordered)
-    chkOrder(lh',lh,Unordered)
+    chkOrder(lh,lh',EqualTo)        (* APB 2008.08.20 Changed this from Unordered.  Also changed the code *)
+    chkOrder(lh',lh,EqualTo)        (* APB 2008.08.20 Changed this from Unordered.  Also changed the code *)
   end